[TJOI2009] 猜数字 - 中国剩余定理

现有两组数字，每组k个，第一组中的数字分别为：a1，a2，...，ak表示，第二组中的数字分别用b1，b2，...，bk表示。其中第二组中的数字是两两互素的。求最小的非负整数n，满足对于任意的i，n - ai能被bi整除。

Solution

即 \(n=a_i \ mod \ b_i\)

裸CRT

但是我很懒所以用了 EXCRT 的板子

（然后发现板子的 Note 又写错了）

#include <bits/stdc++.h>

using namespace std;

#define int long long

namespace excrt {

const int maxn=100010;

int n;

int ai[maxn],bi[maxn]; //x=b%a

int mul(int a,int b,int mod){

    int res=0;

    while(b>0){

        if(b&1) res=(res+a)%mod;

        a=(a+a)%mod;

        b>>=1;

    }

    return res;

}

int exgcd(int a,int b,int &x,int &y){

    if(b==0){x=1;y=0;return a;}

    int gcd=exgcd(b,a%b,x,y);

    int tp=x;

    x=y; y=tp-a/b*y;

    return gcd;

}

int solve(){

    int x,y,k;

    int M=bi[1],ans=ai[1];

    for(int i=2;i<=n;i++){

        int a=M,b=bi[i],c=(ai[i]-ans%b+b)%b;

        int gcd=exgcd(a,b,x,y),bg=b/gcd;

        if(c%gcd!=0) return -1;

        x=mul(x,c/gcd,bg);

        ans+=x*M;

        M*=bg;

        ans=(ans%M+M)%M;

    }

    return (ans%M+M)%M;

}

}

const int N = 15;

int a[N],b[N],n;

signed main() {

    cin>>n;

    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++) cin>>b[i];

    for(int i=1;i<=n;i++) a[i]=(a[i]%b[i]+b[i])%b[i];

    for(int i=1;i<=n;i++) excrt::ai[i]=a[i];

    for(int i=1;i<=n;i++) excrt::bi[i]=b[i];

    excrt::n=n;

    cout<<excrt::solve();

}

巴特西

[TJOI2009] 猜数字 - 中国剩余定理

Solution

最新文章

热门文章