TJOI2009 猜数字

题目:

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

思路:

  中国剩余定理板子题,顺手敲了一下就当练板子了。。。
  注意一下防止爆long long,写下快速模乘防爆,虽然我这个板子并没有爆

代码:

#include <bits/stdc++.h>
#define ll long long
void swap(ll &a,ll &b){a^=b;b^=a;a^=b;}
ll mul(ll a,ll b,ll m){
    a=(a%m+m)%m;b=(b%m+m)%m;
    ll ans=0;
    if(a>b)swap(a,b);
    while(a){
        if(a&1)
            ans=(ans+b)%m;
        b=(b<<1)%m;
        a>>=1;
    }
    return ans;
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
#define lcm(a,b) ((a)/gcd(a,b)*(b))
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(!b){d=a;x=1;y=0;return;}
    exgcd(b,a%b,d,y,x);y-=a/b*x;
}
ll calc(ll a,ll b,ll c){
    ll d,x,y;
    exgcd(a,b,d,x,y);
    if(c%d)return -1;
    b/=d;c/=d;
    return (mul(x,c,b)+b)%b;
}
struct CRT{
    ll A,M;
    CRT(){A=0;M=1;}
    bool insert(ll a,ll m){
        ll k=calc(M,m,a-A);
        if(!~k)return false;
        A+=M*k;
        M=lcm(M,m);
        return true;
    }
};
ll a[15],m[15];
int main(){
    int k;
    scanf("%d",&k);
    for(int i=1;i<=k;i++)
        scanf("%lld",a+i);
    for(int i=1;i<=k;i++)
        scanf("%lld",m+i);
    CRT crt;
    for(int i=1;i<=k;i++)
        crt.insert(a[i],m[i]);
    printf("%lld\n",crt.A);
    return 0;
}