TJOI2009_猜数字(CRT模板题)

题面传送门

题目要求不就是k个线性同余方程$n≡a_{i}(mod\ b_{i})$并且$b_{i}$两两互质吗。

哇出题人好良心啊,直接上CRT。(我才不会告诉你我后面就会给他寄刀片了)

求一个$b_{i}$的$lcm$,然后设$c_{i}=lcm/b_{i}$,求出$c_{i} mod\ b_{i}$的乘法逆元为$t_{i}$.

最后x的一个解肯定是$Σ_{i=1}^n\ a_{i}*t_{i}*c_{i}$ 而题目要求是最小解,我们只需要把x搞到0~lcm-1里面就行了。

你以为结束了吗,并没有,现在才是这道题的开始:

1.求逆元必须用exgcd,并且边求边$mod\ lcm$

2.最后一个点会爆long long,我们要用龟速乘

3.最后答案有可能小于0

4.甚至$a_{i}$都有可能小于0,一开始还要处理$a_{i}=(a_{i}\mod\ b_{i}+b_{i})\mod\ b_{i}$

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<queue>
#include<set>
#define N 15
#define int long long
#define ri register int
using namespace std;
template <class T> void in(T &x) {
    x=0;
    bool flag=0;
    char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-')
            flag=1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=(x<<3)+(x<<1)+(c^48);
        c=getchar();
    }
    if(flag)
        x=-x;
}
int all=1,x,k,yy;
int a[N],b[N],c[N],d[N],e[N];
inline int pow(int x,int y) {
    int res=0;
    while(y) {
        if(y&1)
            res=(res+x)%all;
        x=(x+x)%all;
        y>>=1;
    }
    return res;
}
/*inline int ksm(int x,int k) {
    int ans=1;
    while(k) {
        if(k&1)
            ans=pow(ans,x);
        x=pow(x,x);
        k>>=1;
    }
    return ans%all;
}*/
inline void exgcd(int a,int b,int &x,int &y) {
    if(b==0) {
        x=1;
        y=0;
        return ;
    } else {
        exgcd(b,a%b,y,x);
        y-=(a/b)*x;
    }
}
signed main() {
    in(k);
    for(ri i=1; i<=k; ++i) in(a[i]);
    for(ri i=1; i<=k; ++i) in(b[i]),all*=b[i];
    for(ri i=1; i<=k; ++i) {
        a[i]%=b[i];
        if(a[i]<0)
            a[i]+=b[i];
    }
    for(ri i=1; i<=k; ++i)
        c[i]=all/b[i];
    for(ri i=1; i<=k; ++i) {
        int xx;
        exgcd(c[i],b[i],xx,yy);
        x=(x+pow(pow(xx,c[i]),a[i]))%all;
    }
    /*for(ri i=1; i<=k; ++i)
        printf("%lld %lld %lld %lld\n",a[i],b[i],c[i],d[i]);*/
    if(x<0)
        x+=all;
    printf("%lld",x);
    return 0;
}

发表于 2018-10-05 13:46:22 in 知识点