HDU 1788 模余运算

2019-04-13 21:08发布

站内文章 / 模拟电子
15491 0 1432
题目   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);
    }
}

热门文章