hdu 1370相互質の中国の残りの問題のテンプレート
1432 ワード
こんな変な入出力が大嫌いです.のニマの前にcin>>cを追加しなければなりません.waが爆発しても思い出せないですね.の
#include<iostream>
using namespace std;
const int MAXM=12;
typedef long long int llint;
llint a[]={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 tmp = x; x = y; y = tmp - a/b * y;
return r;
}
long long int lcm(long long int a,long long int b)
{
int x,y;
return (a*b)/(exgcd(a,b,x,y));
}
llint crr(llint a[],llint b[],int n,llint &mt)//x%a=b
{
//llint mt;
mt=1;
int i=0;
for(i=0;i<=n-1;i++)
{
mt=lcm(mt,a[i]);
}
llint result=0;
for(i=0;i<=n-1;i++)
{
llint mi=mt/a[i];
int x,y;
exgcd(mi,a[i],x,y);
result=(result+mi*x*b[i]+mt)%mt;
}
return (result+mt)%mt;
}
int main()
{
llint b[3],d;
int c;
cin>>c;
while(cin>>b[0]>>b[1]>>b[2]>>d)
{
if(b[0]==-1&&b[1]==-1&&b[2]==-1&&d==-1)
{
break;
}
llint mt;
int r=crr(a,b,3,mt)-d;
if(r<=0)
{
r+=mt;
}
cout<<"Case "<<c++<<": the next triple peak occurs in "<<r<<" days."<<endl;
}
return 0;
}