中国剩余定理(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日

相关文章

  • C++线性表深度解析之动态数组与单链表和栈及队列的实现

    C++线性表深度解析之动态数组与单链表和栈及队列的实现 动态数组的实现 动态数组是一种可以动态扩展的数组结构,它的容量可以随着需要而动态增加。在C++中,使用vector类可以实现动态数组的功能。vector类相当于动态分配了一块内存空间,在使用时可以根据需要进行动态扩展。下面是一个示例代码: #include <vector> #include…

    数据结构 2023年5月17日
    00
  • C语言数据结构之堆、堆排序的分析及实现

    C语言数据结构之堆、堆排序的分析及实现 什么是堆 堆(Heap)是一种特殊的树形数据结构,它满足两个条件: 堆是一棵完全二叉树; 堆中任意节点的值总是不大于/不小于其子节点的值。 如果父节点的值不大于所有子节点的值,此堆称为小根堆,又称为最小堆。如果父节点的值不小于所有子节点的值,此堆称为大根堆,又称为最大堆。 堆通常可以使用数组来实现,具体实现方法是将堆的…

    数据结构 2023年5月17日
    00
  • Python实现常见的回文字符串算法

    以下是关于“Python实现常见的回文字符串算法”的完整攻略: 简介 回文字符串是指正着读和倒着读都一样的字符串。在本教程中,我们将介绍如何使用Python实现常见的回文字符串算法,并提供两个示例。 算法1:双指针法 双指针法是一种常见的回文字符串算法,它使用两个指针从字符串的两端开始扫描,如果两个指针指向的字符相同,则继续向中间移动,否则返回false。 …

    python 2023年5月14日
    00
  • C语言线性表全面梳理操作方法

    C语言线性表全面梳理操作方法 线性表概述 线性表是一种常用的数据结构,是指数据元素之间存在一定逻辑顺序,每个元素都有唯一的前驱和后继。 线性表有两种存储方式: 顺序存储结构 和 链式存储结构。 顺序存储结构 顺序存储结构是指采用顺序存储方式存储线性表,即将线性表的元素依次存储在一段连续的存储空间内。 代码示例:创建顺序存储线性表 #define MaxSiz…

    数据结构 2023年5月17日
    00
  • 【ACM博弈论】SG函数入门(1):从巴什博奕到尼姆游戏

    在我小时候以前做题的时候,遇到博弈题往往都是漫无目的地打表找规律,或者找一些特殊情况但是没有很好的分析方法。 其实博弈题是有比较套路的解题方法的,那就是利用SG函数,第一节不会讲到SG函数的具体用法,我们先来博弈入个门,学习一下最基本的博弈类型:Nim游戏。 ? 作者:Eriktse? 简介:19岁,211计算机在读,现役ACM银牌选手?力争以通俗易懂的方式…

    算法与数据结构 2023年4月17日
    00
  • 数据结构 C语言实现循环单链表的实例

    首先,在开始讲解数据结构中循环单链表的实现前,需要明确循环单链表的概念以及其与单链表的区别。 循环单链表是一种链式存储结构,与单链表不同的是,在循环单链表的尾部也可以指向链表的头部,形成一个环。因此,我们可以通过尾部的指针来遍历整个循环单链表。 接下来,为了方便理解和学习,我们将使用C语言来实现循环单链表的实例。下面分几个步骤来讲解。 1. 定义结构体和创建…

    数据结构 2023年5月17日
    00
  • 使用python求解迷宫问题的三种实现方法

    使用Python求解迷宫问题的三种实现方法 迷宫问题是一个经典的寻路问题,目标是从起点到达终点,避免碰到障碍物。在这个攻略中,我们将介绍三种使用Python求解迷宫问题的实现方法:深度优先搜索、广度优先搜索和A*搜索。我们将提供两个示例说明如何使用这些算法来解决迷宫问题。 深度优先搜索 深度优先搜索是一种基于栈的搜索算法,它从起点开始,沿着一条路径一直走到底…

    python 2023年5月14日
    00
  • Python实现计算文件MD5和SHA1的方法示例

    以下是关于“Python实现计算文件MD5和SHA1的方法示例”的完整攻略: 简介 MD5和SHA1是常用的哈希算法,用于计算文件的哈希值。在本教程中,我们将介绍如何使用Python实现计算文件MD5和SHA1的方法,包括使用hashlib库和使用第三方库pycryptodome。 使用hashlib库 hashlib是Python标准库中的一个哈希算法库,…

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