中国剩余定理

说明

中国剩余定理用于求模方程组 方程组形如 x%divisor[i] = rest[i]

使用方法

  1. 将n个方程的模域和余数存入divisor[]和rest[]中,下标从0~n-1
  2. x = CRT1(n)返回值即为一个符合条件的解,其它符合条件的解为 x + Π(divisor[i])

Tips

  1. 考虑数据范围,如果求模域的时候可能爆long long请使用快速乘
  2. 模域是否两两互质下面CRT1CRT2对号入座
const int maxn=1000+5;
typedef long long ll;
ll mult_mod(ll a,ll b,ll mod){
    return (a*b-(ll)(a/(long double)mod*b+1e-3)*mod+mod)%mod;
}

ll ex_gcd(ll a,ll b,ll &x,ll &y){
    if (b==0) {
        x=1,y=0;
        return a;
    }
    else{
        ll res=ex_gcd(b,a%b,y,x);
        y-=x*(a/b);
        return res;
    }
}

// 中国剩余定理 模域两两互质 x%(divisor[i])=rest[i]
ll CRT1(ll divisor[],ll rest[], int n){    //n表示有n个方程,0~n-1
    ll gcd,tmp,product=1,res=0,x,y;
    for (int i=0; i<n; i++)
        product*=divisor[i];
    for (int i=0; i<n; i++) {
        tmp=product/divisor[i];
        gcd=ex_gcd(divisor[i], tmp, x, y);
        res = (res + mult_mod(mult_mod(y, tmp, product), rest[i], product))%product;//防爆
//        res=(res+y*tmp%product*rest[i]%product)%product;
    }
    return (res+ product)%product;//返回值为符合模方程组的解
}

// 中国剩余定理非互质版 有解返回解,无解返回-1 x%(divisor[i])=rest[i]
ll CRT2(ll divisor[], ll rest[], int n) {   //n表示有n个方程,0~n-1
    if (n == 1) {
        if (divisor[0] > rest[0]) return rest[0];
        else return -1;
    }
    ll x, y, d;
    for (int i = 1; i < n; i++) {
        if (divisor[i] <= rest[i]) return -1;
        d = ex_gcd(divisor[0], divisor[i], x, y);
        if ((rest[i] - rest[0]) % d != 0) return -1;
        ll t = divisor[i] / d;
        x = ((rest[i] - rest[0]) / d * x % t + t) % t;
        rest[0] = x * divisor[0] + rest[0];
        divisor[0] = divisor[0] * divisor[i] / d;
        rest[0] = (rest[0] % divisor[0] + divisor[0]) % divisor[0];
    }
    return rest[0];
}

results matching ""

    No results matching ""