中国剩余定理

线性同余方程

在数论中，线性同余方程是最基本的同余方程，“线性”表示方程的未知数次数是一次，即形如：
ax≡b (mod n)的方程。此方程有解当且仅当 b 能够被 a 与 n 的最大公约数整除（记作 gcd(a,n) | b）。这时，如果 x0 是方程的一个解，那么所有的解可以表示为：

• {x0+kn/d|(k∈z)}
• 其中 d 是a 与 n 的最大公约数。在模 n 的完全剩余系 {0,1,…,n-1} 中，恰有 d 个解。

解释

这就是线性同余方程 ax = b + t*mod
若有解x0，则解集 X = x+k*n/gcd(a,mod)
如果 b % gcd(a,mod) != 0 ,则无解。

例子

3x ≡ 2 (mod 6)
中， d = gcd(3,6) = 3 ，3 不整除 2，因此方程无解。

---

5x ≡ 2 (mod 6)
中， d = gcd(5,6) = 1，1 整除 2，因此方程在{0,1,2,3,4,5} 中恰有一个解: x=4。

---

4x ≡ 2 (mod 6)
中， d = gcd(4,6) = 2，2 整除 2，因此方程在{0,1,2,3,4,5} 中恰有两个解: x=2 and x=5。

c++代码

#include <iostream>  
#include <cstdio>  
#include <cstring>  
using namespace std;
#define ll long long  
int ans[1000];  
ll extend_gcd(ll a, ll b, ll &x, ll &y,ll &d)//求解ax+by=gcd(a,b),d是存gcd(a,b)的
{
     if (b == 0) {
        x = 1, y = 0 , d = a;
        return a;
     }
    else{
            ll r = extend_gcd(b, a % b, y, x,d); //递归求解
            y -= x * (a / b);
            return r;
    }//x=(x%b+b)%b x的最小整数解
}
int main()  
{  
    ll a,b,m;  
    ll d,x,y;  
    cout<<"in these style ax=b(mod m)"<<endl;
    while(cin>>a>>b>>m){  
        ll tmp=extend_gcd(a,m,x,y,d);  
        if(b%d){  
            cout<<"No answer"<<endl;  
        }  
        else{  
            x=x*(b/d)%m;  
            cout<<"ans between 0 - "<<m-1<<endl;
            for(int i=1;i<=d;i++){  
                ans[i]=((x+(i-1)*m/d)%m+m)%m;  
                cout<<ans[i]<<" ";  
            }  
            cout<<endl;  
        }  
    }  
    return 0;  
}

中国在剩余定理

中国剩余定理就是线性同余方程组，求解。

例子

三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。

c++代码

#include <iostream>  
#include <cstdio>
using namespace std;  
#define ll long long
/*=========================================
    扩展欧几里得
    求出A，B的最大公约数，且求出X，Y满足AX + BY = GCD(A,B)
    复杂度：O(logN)
=========================================*/
ll extend_gcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    else {
        ll r = extend_gcd(b, a % b, y, x);
        y -= x * (a / b);
        return r;
    }
}

/*=========================================
    中国剩余定理(两两互质)a[i]之间两两互质
    复杂度: O(NlogN)
    输入a,m   第i个方程表示为x ≡ ai(mod mi)
    n   表示方程个数
=========================================*/
const int maxn = 20;
ll a[maxn], m[maxn], n;
ll CRT(ll a[], ll m[], int 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];
        extend_gcd(tm, m[i], x, y);
        ret = (ret + tm * x * a[i]) % M;
    }
    return (ret + M) % M;
}

/*=========================================
    中国剩余定理非互质版
    输入a,m   第i个方程表示为x ≡ ai(mod mi)
    如果有解返回解，无解返回-1
    复杂度：O(NlogN)
=========================================*/
ll CRT2(ll a[], ll m[], int 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 = extend_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;
        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];
}
  
int main()  
{  
    cout<<" X = a (mod m) "<<endl<<"puts the lenths of arry first"<<endl;
    while (scanf("%I64d",&n),n)     
    {  
        for (int i=0;i<n;i++)  
        {  
            scanf("%I64d%I64d",&a[i],&m[i]);  
        }  
        printf("CRT = %I64d \n",CRT(a,m,n));  
        printf("CRT2 = %I64d \n",CRT2(a,m,n)); 
    }  
    return 0;  
}