NOIP模板复习 _ 中国剩余定理(CRT) – [模板]

#define ll long long
ll inv(int a, int p) {
    // 求逆元 
    /*
    int x, y, d;
    exgcd(a, p, d, x, y);
    if(d == 1) return (x%p+p)%p;
    */
    /*
    return qp(a, p-2, p);
    */
    return -1;
}
ll CRT(ll *a, int *m) {
    ll M = 1, res = 0;
    for(int i = 1; i <= *m; i ++ ) M *= m[i];
    for(int i = 1; i <= *m; i ++ ) {
        ll tmp = M/m[i];
        res = (res+tmp*inv(tmp, m[i])%M*a[i])%M;
    }
    return (res+M)%M;
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注