[POJ1006] Biorhythms 中国剩余定理

[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_1p_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;
}

留下回复