コンソールHDU 1788 Chinese remander theoromagainのデジタル理論を読んでコンソールを読みます.
3696 ワード
愚痴を言ってもテーマは関係ありません.
目的地: http://acm.hdu.edu.cn/showproblem.php?pid=1788
NはM 1余(M 1-a)で割り、M 2余(M 2-a)で割り、M 3余(M 3-a)で割る.つまり、MI余(MI-a)で割る.
最小のNを求める
第一の解法:直接に題意に従って行う(孫の定理)
生活のしようがなさ、時には決して自己から源を発しなくて、他の人の気がない築いて、あれは1種の日陰の差の陽の誤りです.生活は元来矛盾していて、昼と夜の間の距離、春夏秋冬の間の巡回、そこでけちをつける好みがあって、しようがなく喜びの待つことを加えました.
第二の解法:
M 1、M 2、、、Mnの最小公倍数を求めて、そしてlcm-a、全部余aですから.
目的地: http://acm.hdu.edu.cn/showproblem.php?pid=1788
NはM 1余(M 1-a)で割り、M 2余(M 2-a)で割り、M 3余(M 3-a)で割る.つまり、MI余(MI-a)で割る.
最小のNを求める
第一の解法:直接に題意に従って行う(孫の定理)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;
/*
freopen("input.txt", "r", stdin); //
freopen("output.txt", "w", stdout); //
*/
typedef __int64 LL;
LL w[15],b[15];
int n;
// Euclid gcd(a,b)=ax+by
LL ext_gcd(LL a,LL b,LL& x,LL& y)
{
LL t,ret;
if (!b)
{
x=1,y=0;
return a;
}
ret=ext_gcd(b,a%b,x,y);
t=x,x=y,y=t-a/b*y;
return ret;
}
LL China_left2()
{
LL w1,w2,b1,b2,gcd,x,y,t;
int i,flag;
flag=0;w1=w[0];b1=b[0];
for(i=1;i<n;i++)
{
w2=w[i];b2=b[i];
gcd=ext_gcd(w1,w2,x,y);
if((b2-b1)%gcd)
{
flag=1;break;
}
t=w2/gcd;
x=(x*(b2-b1))/gcd;
x=(x%t+t)%t;
b1=w1*x+b1;
w1=(w1*w2)/gcd;
b1=(b1%w1+w1)%w1;
}
if(flag==1)
b1=-1;
if(b1==0&&n>1)
b1=w1;
if(b1==0&&n==1)
b1=w[0];
return b1;
}
int main()
{
int i,a;
while(cin>>n>>a&&n+a)
{
for(i=0;i<n;i++)
{
scanf("%I64d",&w[i]);
b[i]=w[i]-a;
}
printf("%I64d
",China_left2());
}
return 0;
}生活のしようがなさ、時には決して自己から源を発しなくて、他の人の気がない築いて、あれは1種の日陰の差の陽の誤りです.生活は元来矛盾していて、昼と夜の間の距離、春夏秋冬の間の巡回、そこでけちをつける好みがあって、しようがなく喜びの待つことを加えました.
第二の解法:
M 1、M 2、、、Mnの最小公倍数を求めて、そしてlcm-a、全部余aですから.
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
using namespace std;
/*
freopen("input.txt", "r", stdin); //
freopen("output.txt", "w", stdout); //
*/
typedef __int64 LL;
LL w[11];
LL gcd(LL m,LL n)//
{
LL t;
while(n)
{ t=m%n; m=n; n=t; }
return m;
}
int main()
{
int i,a,n;
while(cin>>n>>a&&n+a)
{
LL xiaohao=1;
for(i=0;i<n;i++)
{
scanf("%I64d",&w[i]);
xiaohao=(xiaohao/gcd(xiaohao,w[i])*w[i]);
}
printf("%I64d
",xiaohao-a);
}
return 0;
}