题目
http://acm.hdu.edu.cn/showproblem.php?pid=1788
题意:中文..
解题思路:模余运算,模板题,目前自己不能直接拍出来,但是理解它绝对没问题...
#include
#include
using namespace std;
typedef __int64 int64;
int64 a[30],b[30],mod;
int64 gcd(int64 x,int64 y){
if(y==0) return x;
return gcd(y,x%y);
}
int64 Ext_eud(int64 a,int64 b,int64 &x,int64 &y){
if(b==0) {
x=1;y=0;
return a;
}
int64 d=Ext_eud(b,a%b,x,y);
int64 t=x;
x=y;
y=t-a/b*y;
return d;
}
int64 inv(int64 a,int64 n){
int64 x,y;
int64 t=Ext_eud(a,n,x,y);
if(t!=1) return -1;
return ( x%n+n )%n;
}
bool merge( int64 a1,int64 n1,int64 a2,int64 n2,int64 &a3,int64 &n3 ){
int64 d=gcd(n1,n2);
int64 c=a2-a1;
if(c%d) return false;
c=(c%n2+n2)%n2;
c/=d;
n1/=d;
n2/=d;
c*=inv(n1,n2); /// 逆元
c%=n2;
c*=n1*d;
c += a1;
n3 = n1*n2*d;
a3 = ( c%n3+n3 )%n3;
return true;
}
int64 china_reminder(int64 len,int64*a,int64*n){
int64 a1=a[0],n1=n[0];
int64 a2,n2;
for(int i=1;i
int64 aa,nn;
a2=a[i],n2=n[i];
if(!merge(a1,n1,a2,n2,aa,nn)){
return -1;
}
a1=aa;
n1=nn;
}
mod=n1;
return (a1%n1+n1)%n1;
}
int main(){
int num,k;
while(cin>>num>>k,num || k){
int64 lcm=1;
for(int i=0;i
scanf("%I64d",&a[i]); /// a[] 除数
lcm = a[i]/gcd( lcm,a[i] )*lcm;
b[i]=a[i]-k; /// b[]余数
}
int64 sum=china_reminder(num,b,a);
while(sum<0)
sum += lcm;
printf("%I64d
",sum);
}
}