中国剩余定理(CRT)学习笔记

约定

  • \(A\perp B\) 表示 \(\gcd(A,B)=1\)
  • \(A\mid B\) 表示 \(B\equiv 0\pmod{A}(A\neq0)\)

引入

考虑以下这道题:

有物不知其數,三三數之剩二,五五數之剩三,七七數之剩二。 問物幾何?—— 《孫子算經》

也就是说,求出下列关于 \(x\) 方程组的最小整数解:

\[\begin{cases}
x\equiv2\pmod{3}\\
x\equiv3\pmod{5}\\
x\equiv2\pmod{7}
\end{cases}
\]

解析

首先我们考虑什么时候 \(\equiv3\pmod{3}\),什么时候 \(\equiv3\pmod{5}\),什么时候 \(\equiv2\pmod{7}\)。也就是解下面的方程:

\[\begin{cases}
x_1\equiv2\pmod{3}\\
x_2\equiv3\pmod{5}\\
x_3\equiv2\pmod{7}
\end{cases}
\]

解得:

\[\begin{cases}
x_1=3k_1+2&(k_1\in\mathbb{Z})\\
x_2=5k_2+3&(k_2\in\mathbb{Z})\\
x_3=7k_3+2&(k_3\in\mathbb{Z})\\
\end{cases}
\]

但这个解毫无用处。因为我们无法直接从 \(x_1,x_2,x_3\) 求出 \(x\)

一种常见的想法是,取 \(x=x_1+x_2+x_3\)。那我们就有结论 \(x_1+x_2\equiv2\pmod{3}\)

这个结论显然只在 \(3\mid x_2\) 时成立。

因此我们可以得到,令 \(x_1=(5\cdot7)y_1,x_2=(3\cdot7)y_2,x_3=(3\cdot5)y_3\),则:

\[\begin{cases}
35y_1\equiv2\pmod{3}\\
21y_2\equiv3\pmod{5}\\
15y_3\equiv2\pmod{7}
\end{cases}
\]

然后发现 \(\equiv\) 右边的数字不是 \(1\) 就非常烦。我们令 \(z_1=2y_1,z_2=3y_2,z_3=2y_3\),再分别约去 \(2,3,2\) 得到:

\[\begin{cases}
35z_1\equiv1\pmod{3}\\
21z_2\equiv1\pmod{5}\\
15z_3\equiv1\pmod{7}
\end{cases}
\]

注意到 \(3\perp5\perp7\),则 \(35\perp3,21\perp5,15\perp7\)。所以存在逆元(存在 \(z_1,z_2,z_3\))。这个可以用扩展欧几里得或者线性求逆元来求出 \(z_1=2,z_2=1,z_3=1\)

\(y_1=4,y_2=3,y_3=2\)\(x_1=140,x_2,=63,x_3=30\)。则 \(x=233\)

但是 \(233\) 并不是最小正整数解。不难发现只要 \(a\equiv b\pmod{3\cdot5\cdot7}\),那么 \(a,b\) 都是合法解。

所以最小正整数解是 \(233\bmod (3\cdot5\cdot7)=23\)

整理

现在,我们就得到了求解下列方程组的通法:

\[\begin{cases}
x\equiv b_1\pmod{a_1}\\
x\equiv b_2\pmod{a_2}\\
\cdots\cdots\cdots\cdots\cdots\cdot\cdot\\
x\equiv b_n\pmod{a_n}\\
\end{cases}
\]

其中 \(a_1\perp a_2\perp\cdots a_n\)

  • 求出 \(K=\prod_{i=1}^{n}a_i\)

  • 对于 \(1 \leq i \leq n\),解关于 \(z_i\) 的方程 \(\dfrac{K}{a_i}\cdot z_i\equiv1\pmod{a_i}\)

  • 计算 \(y_i=b_i\cdot z_i \cdot \dfrac{K}{a_i}\)

  • 则最小整数解 \(x=\sum_{i=1}^{n}{y_i} \bmod K\)

例题

P1495 【模板】中国剩余定理(CRT)/ 曹冲养猪

给出两个长为 \(n\) 的序列 \(a,b\)。求以下关于 \(x\) 的方程组的最小整数解:

\[\begin{cases}
x\equiv b_1\pmod{a_1}\\
x\equiv b_2\pmod{a_2}\\
\cdots\cdots\cdots\cdots\cdots\cdot\cdot\\
x\equiv b_n\pmod{a_n}\\
\end{cases}
\]

\(1 \leq n \leq 10\)

模板题。大家可以参考一下我的代码实现:

#include <bits/stdc++.h>
#define int long long
using namespace std;

void exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;
		y=0;
	}
	else{
		exgcd(b,a%b,x,y);
		int tmp=x;
		x=y;
		y=tmp-a/b*y;
	}
}

int n,a[15],b[15];

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    int K=1,x=0;
    for(int i=1;i<=n;i++) K*=a[i];
    for(int i=1;i<=n;i++){
        int z=0,ytxy=0,y=0;
        exgcd(K/a[i],a[i],z,ytxy);
        z=((z%a[i]+a[i])%a[i]);
        y=b[i]*z*(K/a[i]);
        x+=y;
    }
    cout<<((x%K+K)%K);
    return 0;
}

原文链接:https://www.cnblogs.com/zheyuanxie/p/crt.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:中国剩余定理(CRT)学习笔记 - Python技术站

(0)
上一篇 2023年4月30日
下一篇 2023年4月30日

相关文章

  • Python实现的数据结构与算法之基本搜索详解

    Python实现的数据结构与算法之基本搜索详解 在计算机科学中,搜索指的是在一组数据中找到目标数据的过程。搜索算法是解决各种问题的关键,即使是拼图游戏和图像识别也要依赖搜索算法。本文将介绍基本的搜索算法,包括线性/顺序搜索、二分搜索和广度优先搜索。 线性/顺序搜索 顺序搜索又称为线性搜索,它遍历整个数据集以查找特定元素。顺序搜索可以用于查找未排序的列表。该算…

    数据结构 2023年5月17日
    00
  • Python实现贪心算法的示例

    下面是详细讲解“Python实现贪心算法的示例”的完整攻略,包括算法原理、Python实现和两个示例。 算法原理 贪心算法是一种基于贪心略的优化算法,其基本思想是在每一步选择都采取当前状态下最优的选择,从而希望最终得到局最优解。贪心算法通常适用于满足贪心选择性质和最优子结性质的问题。具体步骤如下: 将问题分解为若干个子; 对每个子问题进行贪心选择,即当前状态…

    python 2023年5月14日
    00
  • Java数据结构之加权无向图的设计实现

    Java数据结构之加权无向图的设计实现 前言 在计算机科学中,图(Graph)作为一种基本数据结构,被广泛应用于各种领域,如网络流、图像处理、计算机视觉等。本文将介绍加权无向图(Weighted Undirected Graph)的设计实现,涉及图的存储、添加边、获取特定节点的相邻节点、计算最短路径等。 设计实现 存储结构 加权无向图可以用一个邻接表数组存储…

    数据结构 2023年5月17日
    00
  • C++数据结构与算法之双缓存队列实现方法详解

    C++数据结构与算法之双缓存队列实现方法详解 引言 在实际开发中,双缓存队列是一个非常常见的数据结构,主要用来解决多线程情况下的数据同步问题。本篇文章将详细介绍如何使用C++语言实现双缓存队列。 双缓存队列简介 双缓存队列是一种常用的同步数据结构,它并非一个标准库中的容器,通常需要手动实现。双缓存队列维护着两个缓存区,一个当前使用的缓存区,一个需要被更新的缓…

    数据结构 2023年5月17日
    00
  • 数据结构 双机调度问题的实例详解

    数据结构:双机调度问题的实例详解 本文主要讲解数据结构中双机调度问题的实例详解,涉及到相关的算法和代码实现。双机调度问题是指如何安排多个任务在两台机器上执行,使得两台机器的工作时间尽可能相等,从而达到最优的调度效果。 1. 问题分析 假设有 $n$ 个任务,每个任务的执行时间分别为 $t_1, t_2, …, t_n$,需要按照某种调度方案分配给两台机器…

    数据结构 2023年5月17日
    00
  • TypeScript数据结构栈结构Stack教程示例

    下面就给您详细讲解一下“TypeScript数据结构栈结构Stack教程示例”的完整攻略。 1. 栈结构(Stack)概述 栈是一种特殊的数据结构,它的特点是后进先出(Last In First Out,LIFO)。和数组不同的是,栈只能在栈顶插入和删除元素。栈的常见操作有“- push() 元素入栈,将元素放到栈顶- pop() 元素出栈,从栈顶取出元素…

    数据结构 2023年5月17日
    00
  • 四边形不等式学习笔记

    简要题意 四边形不等式是一种 dp 优化策略。多用于 2D DP。 内容 对于区间 \([l,r]\) 带来的贡献 \(w(l,r)\),如果其满足: 对于 \(L\leq l\leq r \leq R\),\(w(L,r)+w(l,R)\leq w(L,R)+w(l,r)\) 则称 \(w\) 满足四边形不等式。特别地,如果上式符号取等,则称其满足四边形恒…

    算法与数据结构 2023年4月17日
    00
  • python opencv之SURF算法示例

    Python OpenCV之SURF算法示例 本文将介绍如何使用Python OpenCV库实现SURF算法,并提供两个示例说明。 SURF算法简介 SURF(Speeded Up Robust Features)算是一种用于图像特征提取和匹配的算法。它是SIFT算法改进版本,具有更快的速度和更好的鲁棒性。SURF算法的要步骤包括构建尺度空间、算Hessia…

    python 2023年5月14日
    00
合作推广
合作推广
分享本页
返回顶部