中国剩余定理#

定义#

中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组（其中 两两互质）：

过程#

1. 计算所有模数的积 ；
2. 对于第 个方程：
   1. 计算 ；
   2. 计算 在模 意义下的逆元 ；
   3. 计算 （不要对 取模）。
3. 方程组在模 意义下的唯一解为：。

证明#

我们需要证明上面算法计算所得的 对于任意 满足 。

当 时，有 ，故 。 当 时, 有 ，所以我们有：

即对于任意 ，上面算法得到的 总是满足 ，即证明了解同余方程组的算法的正确性。

因为我们没有对输入的 作特殊限制，所以任何一组输入 都对应一个解 。

另外，若 ，则总存在 使得 和 在模 下不同余。

故系数列表 与解 之间是一一映射关系，方程组总是有唯一解。

实现#

int CRT(int a[], int n[]){
    int N=1, ans=0;
    for(int i =1;i<=n;i++) N*=n[i];//计算所有模数的乘积
    for(int i = 1;i<=n;i++){
        int c=N/n[i],x,y;
        exgcd(c,n[i],x,y);//exgcd求逆元 其中x即为逆元
        (ans+=(a[i]*c*x%N))%=N;
    }
    return (ans%N+N)%N;//映射到范围内的最小整数
}

拓展中国剩余定理#

定义#

拓展中国剩余定理可求解如下形式的一元线性同余方程组（其中 不一定两两互质）：

此时CRT已不可行

其构造解
其中, 即 根据裴蜀定理，应该互质，
如果不互质，则不存在，算法无效

过程#

1. 前两个方程：
   转化为不定方程：,
   则
2. 由裴蜀定理，
   当时，无解 当时，有解
   可以通过扩展欧几里得算法解出来一组可行解 ；
3. 则原来的两方程组成的模方程组的解 ，其中 ，。
4. 多个方程按照至合并即可，个方程合并次。

实现#

long long mul(long long a,long long b,long long mod)
{
    long long c=a*b-(long long)((long double)a*b/mod+0.5)*mod;
    return c<0?c+mod:c;
}//有些情况下会暴longlong 用龟速乘解决一下
long long exCRT(){
    for(long long i = 2,x,y;i<=n;i++){
        long long d=exgcd(m[i-1],m[i],x,y);
        if((r[i]-r[i-1])%d!=0)return -1;
        x=mul(x,((r[i]-r[i-1])/d),(m[i]/d));
        x=(x%(m[i]/d)+m[i]/d)%(m[i]/d);
        r[i]=m[i-1]*x+r[i-1];
        m[i]=m[i-1]*m[i]/d;
    }
    return (r[n]%m[n]+m[n])%m[n];//区范围内最小正值
}