中国剩余定理

本文转载自zwzwzwh博主
附上自己的代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=16;
ll x,y,a[maxn],b[maxn];
int n;
void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(!b)	x=1,y=0;
	else	exgcd(b,a%b,y,x),y-=a/b*x;
}
ll sonson()
{
	ll M=1,ans=0;
	for(int i=1;i<=n;i++)	M*=a[i];
	for(int i=1;i<=n;i++)
	{
		x=0,y=0;
		ll m=M/a[i]; exgcd(m,a[i],x,y);
		ans=(ans+m*x*b[i])%M;
	}
	ans=(ans%M+M)%M;
	return ans;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)	cin>>a[i]>>b[i];//除数和余数 
	cout<<sonson();
}

中国剩余定理的具体描述是这样的：

给出你n个ai和mi，最后让求出x的最小值是多少。

中国剩余定理说明：假设整数 $m 1, m 2, ... , m n$ 两两互质，则对任意的整数： $a 1, a 2, ... , a n$ ，方程组 $(S)$ 有解，并且通解可以用如下方式构造得到：

设 $M = m_1 imes m_2 imes cdots imes m_n = prod_{i=1}^n m_i$ 是整数 $m 1, m 2, ... , m n$ 的乘积，并设 $M_i = M/m_i, ; ; forall i in {1, 2, cdots , n}$ 是除了 $m i$ 以外的 $n - 1$ 个整数的乘积。
设 $t_i = M_i^{-1}$ 为 $M_i$ 模 $m_i$ 的数论倒数： $t_i M_i equiv 1 pmod {m_i}, ; ; forall i in {1, 2, cdots , n}.$
方程组 $(S)$ 的通解形式为： $x = a_1 t_1 M_1 + a_2 t_2 M_2 + cdots + a_n t_n M_n + k M= k M + sum_{i=1}^n a_i t_i M_i, quad k in mathbb{Z}.$ 在模 $M$ 的意义下，方程组 $(S)$ 只有一个解： $x = sum_{i=1}^n a_i t_i M_i.$

分割线

下面我们来看一个具体的例子：

使用中国剩余定理来求解上面的“物不知数”问题，便可以理解《孙子歌诀》中的数字含义。这里的线性同余方程组是：

(S) : quad left{ egin{matrix} x equiv 2 pmod {3} \ x equiv 3 pmod {5} \ x equiv 2 pmod {7} end{matrix} ight.

三个模数 $m 1$ $=$ 3, $m 2$ $=$ 5, $m 3$ $=$ 7的乘积是 $M$ $=$ 105，对应的 $M 1$ $=$ 35, $M 2$ $=$ 21, $M 3$ $=$ 15. 而可以计算出相应的数论倒数： $t 1$ $=$ 2, $t 2$ $=$ 1, $t 3$ $=$ 1. 所以《孙子歌诀》中的70，21和15其实是这个“物不知数”问题的基础解：

70 = 2 imes 35 equiv left{ egin{matrix} 1 pmod {3} \ 0 pmod {5} \ 0 pmod {7} end{matrix} , ight. 21 = 1 imes 21 equiv left{ egin{matrix} 0 pmod {3} \ 1 pmod {5} \ 0 pmod {7} end{matrix} , ight. 15 = 1 imes 15 equiv left{ egin{matrix} 0 pmod {3} \ 0 pmod {5} \ 1 pmod {7} end{matrix} , ight.

而将原方程组中的余数相应地乘到这三个基础解上，再加起来，其和就是原方程组的解：

2 imes 70 + 3 imes 21 + 2 imes 15 equiv left{ egin{matrix} 2 imes 1 + 3 imes 0 + 2 imes 0 equiv 2 pmod {3} \ 2 imes 0 + 3 imes 1 + 2 imes 0 equiv 3 pmod {5} \ 2 imes 0 + 3 imes 0 + 2 imes 1 equiv 2 pmod {7} end{matrix} , ight.

这个和是233，实际上原方程组的通解公式为：

x = 233 + k imes 105, ; kin mathbb{Z}.

《孙子算经》中实际上给出了最小正整数解，也就是 $k$ $=$ -2时的解： $x$ $=$ 23.

附：数论倒数 wiki

具体代码参考如下：（应该很明了）


///n个mi互质
const LL maxn = 20;
LL a[maxn], m[maxn], n;
LL CRT(LL a[], LL m[], LL n)
{
    LL M = 1;
    for (int i = 0; i < n; i++) M *= m[i];
    LL ret = 0;
    for (int i = 0; i < n; i++)
    {
        LL x, y;
        LL tm = M / m[i];
        ex_gcd(tm, m[i], x, y);
        ret = (ret + tm * x * a[i]) % M;
    }
    return (ret + M) % M;
}

分割线

下面也就是关于这个的扩展，前面我们已经说了，中国剩余数定理是适用于n个mi两两互质的情况的，如果不互质呢，下面就是一个转换：

模不两两互质的同余式组可化为模两两互质的同余式组，再用孙子定理直接求解。

84=2²×3×7,160=2⁵×5,63=3²×7，由推广的孙子定理可得 $egin{cases}x equiv 23 pmod{84} \x equiv 7 pmod{160} \x equiv 2 pmod{63} end{cases}$ 与 $egin{cases}x equiv 7 pmod{2^5} \x equiv 2 pmod{3^2} \x equiv 7 pmod{5} \x equiv 23 pmod{7}end{cases}$ 同解。

附图：详细讲解，转自传送门


///n个mi不互质
const LL maxn = 1000;
LL a[maxn], m[maxn], n;
LL CRT(LL a[], LL m[], LL n) {
    if (n == 1) {
        if (m[0] > a[0]) return a[0];
        else return -1;
    }
    LL x, y, d;
    for (int i = 1; i < n; i++) {
        if (m[i] <= a[i]) return -1;
        d = ex_gcd(m[0], m[i], x, y);
        if ((a[i] - a[0]) % d != 0) return -1;   //不能整除则无解
        LL t = m[i] / d;
        x = ((a[i] - a[0]) / d * x % t + t) % t; //第0个与第i个模线性方程的特解
        a[0] = x * m[0] + a[0];
        m[0] = m[0] * m[i] / d;
        a[0] = (a[0] % m[0] + m[0]) % m[0];
    }
    return a[0];
}

以上大部分内容来自wiki

下面做几道练手的题目：

poj2891，n个mi不互质的裸题

代码

poj1006，三个互质的裸题

代码