PKU POJ 1006 Biorhythms (中国剩余定理)

中国剩余定理

x = ai (mod mi)  ai和mi是一组数,mi两两互质,求x

令Mi = m1*m2*~mk     其中,mi不包含在内。

因为mi两两互质,所以存在x和y,

st   Mi*xi + mi*yi = 1

令ei = Mi*xi ,则有:

则e0a0 + e1a1 + e2a2+ ~ +en-1*an-1是方程一个解

因为n%3=2,n%5=3,n%7=2且3,5,7互质 
      使5×7被3除余1,用35×2=70; 
       使3×7被5除余1,用21×1=21; 
       使3×5被7除余1,用15×1=15。 
      (70×2+21×3+15×2)%(3×5×7)=23 

   同样,这道题也应该是: 
       使33×28被23除余1,用33×28×8=5544; 
       使23×33被28除余1,用23×33×19=14421; 
       使23×28被33除余1,用23×28×2=1288。 
      (5544×p+14421×e+1288×i)%(23×28×33)=n+d 
       n=(5544×p+14421×e+1288×i-d)%(23×28×33)

#include<stdio.h>
#define P 5544
#define E 14421
#define I 1288
#define ans 21252
int main(void)
{
    int p,e,i,d;
    int n,num=0;
    while(scanf("%d%d%d%d",&p,&e,&i,&d))
    {
        if(p==-1) return 0;
        n=(P*p+E*e+I*i-d+ans)%ans;
        if(n==0) n=ans;
        printf("Case %d: the next triple peak occurs in %d days.
",++num,n);
    }
    return 0;
}
原文地址:https://www.cnblogs.com/woshijishu3/p/3861604.html