首页 > 代码库 > poj1006 ( hdu1370 ):中国剩余定理裸题

poj1006 ( hdu1370 ):中国剩余定理裸题

裸题,没什么好说的

第一个中国剩余定理

写暴力都过了。。可见这题有多水

代码:

#include<iostream>#include<stdio.h>#include<math.h>#include<string>#include<map>#include<algorithm>using namespace std;#define MAX 200000000#define ull unsigned long longconst int MAXN = 100011;int a[3];int m[3]={23,28,33};int exgcd(int a,int b,int &x,int &y){    if(b==0)    {        x=1;y=0;        return a;    }    int r=exgcd(b,a%b,x,y);    int t=x;    x=y;    y=(t-a/b*y);    return r;}int china(int n){    int M=1;    int ans=0;    int x,y,d;    for(int i=0;i<n;i++)    {        M*=m[i];    }    for(int i=0;i<n;i++)    {        int mi=M/m[i];        int x,y;        d=exgcd(mi,m[i],x,y);        ans=(ans+a[i]*mi*x)%M;    }    while(ans<0)        ans+=M;    return ans;} int main() {     int t;     scanf("%d",&t);     while(t--)     {         getchar();         int p,e,d,n,x,f;         int tt=0;         int ans=21252;         while(scanf("%d%d%d%d",&a[0],&a[1],&a[2],&d)&&(a[0]!=-1||a[1]!=-1||a[2]!=-1||d!=-1))         {             tt++;             ans=china(3);             while(ans<=d)                 ans+=21252;             printf("Case %d: the next triple peak occurs in %d days.\n",tt,ans-d);         }         while(t)             printf("\n");     }    return 0;}

 

poj1006 ( hdu1370 ):中国剩余定理裸题