[POJ1006] Biorhythms 中国剩余定理

当我们遇到关于x的形如ax\equiv 1 (\mod p)的同余方程时(gcd(a,p)=1)，我们可以将其转化为求解方程ax+py=1的整数解。这个方程我们可以使用扩展欧几里得算法求解。但是当我们遇到形如

\begin{cases}
x\equiv a_1(\mod p_1) \
x\equiv a_2(\mod p_2) \
\cdots\cdots \
x\equiv a_n(\mod p_n)
\end{cases}
的方程组时(p_1至p_n两两互质)，我们就应该使用中国剩余定理进行求解了。
中国剩余定理的核心思想是将上述方程组转化为求解n个形如
\begin{cases}
x\equiv 1(\mod p_1) \
x\equiv 0(\mod p_2) \
\cdots\cdots \
x\equiv 0(\mod p_n)
\end{cases}
\begin{cases} x\equiv 0(\mod p_1) \
x \equiv 1(\mod p_2) \
\cdots\cdots \
x \equiv 0(\mod p_n)
\end{cases}
\cdots\cdots
\begin{cases}
x \equiv 0(\mod p_1) \
x \equiv 0(\mod p_2) \
\cdots\cdots \
x \equiv 1(\mod p_n)
\end{cases}
的方程组的解。不妨设第i个方程组的解为x_i。显然，最终的答案即为\sum^n_{i=1}a_ix_i(在模P=\Pi_{i=1}^np_i的意义下)
我们不妨考虑对
\begin{cases}
x\equiv 1(\mod p_1) \
x\equiv 0(\mod p_2) \
\cdots\cdots \
x\equiv 0(\mod p_n)
\end{cases}
方程组进行求解
考虑第2个到第n个方程。我们可以设x_1=x\times\Pi_{i=2}^np_i=x\frac{\Pi_{i=1}^np_i}{p_1}=\frac{xP}{p_1}
带入第一个式子得到\frac{P}{p_1}x\equiv 1(\mod p_1)
即可转化为求解\frac{P}{p_1}x+p_1y=1的整数解设为x’
故x_1=x’\times\frac{P}{p_1}
同理可以求得x_2,x_3,\cdots,x_n
问题得到解决

例题 POJ1006 Biorhythms

由于23 28 33互质，直接用crt即可

#include<iostream>
#include<cstdio>
using namespace std;
long long exgcd(long long a,long long b,long long &x,long long &y){
    if(!b){ x=1; y=0; return a; }
    int ans=exgcd(b,a%b,x,y);
    int tmp=x;
    x=y;
    y=tmp-a/b*y;
    return ans;
}
int cnt;
long long m[4]={23,28,33},M=1,r[4];
int main(){
    for(int i=0;i<3;++i) M*=m[i];
    while(1){
        ++cnt;
        long long p,e,i,d;
        long long anss=0;
        for(int i=0;i<3;++i) scanf("%lld",&r[i]);
        scanf("%lld",&d);
        if(d==-1) return 0;
        for(int i=0;i<3;++i){
            long long m_=M/m[i],x,y;
            exgcd(m_,m[i],x,y);
            (x*=m_)%=M;
            (anss+=x*r[i])%=M;
        }
        (((anss-=d)%=M)+=M)%=M;
        printf("Case %d: the next triple peak occurs in %lld days.\n",cnt,anss==0?21252:anss);
    }
    return 0;
}