HDU3579 Hello Kiki 解线性同余方程的应用

 

很典型的看出 x≡Ai(mod Mi)求解，解线性同余方程的应用，

写完一直WA，后来仔细一看，题目要求输出的是最小的正整数解，所以当同余方程组的解为0的时候，就要输出 Mi 的最小公倍数

估计没少有人被坑吧

 

 
#include<iostream>  
#include<cstdio>  
#include<list>  
#include<algorithm>  
#include<cstring>  
#include<string>  
#include<queue>  
#include<stack>  
#include<map>  
#include<vector>  
#include<cmath>  
#include<memory.h>  
#include<set>  
  
#define ll long long  
#define LL __int64  
#define eps 1e-8  
#define e 2.718281828  
  
//const ll INF=9999999999999;  
  
#define M 400000100  
  
#define inf 0xfffffff  
  
using namespace std;  
  
//vector<pair<int,int> > G;  
//typedef pair<int,int> P;  
//vector<pair<int,int>> ::iterator iter;  
//  
//map<ll,int>mp;  
//map<ll,int>::iterator p;  
//  
//vector<int>G[30012];  
  
ll aa[12],rr[12];  
  
ll GCD(ll a,ll b)  
{  
    if(b==0)  
        return a;  
    return GCD(b,a%b);  
}  
  
ll exgcd(ll a,ll &x,ll b,ll &y)  
{  
    if(b==0)  
    {  
        x=1;  
        y=0;  
        return a;  
    }  
    ll r=exgcd(b,x,a%b,y);  
    ll tmp=x;  
    x=y;  
    y=tmp-a/b*y;  
    return r;  
}  
  
int main(void)  
{  
    int t;  
    int Case=0;  
    ll n;  
    cin>>t;  
    while(t--)  
    {  
        cin>>n;  
        ll lcm=1;  
        for(int i=0;i<n;i++)  
        {  
            cin>>aa[i];  
            lcm=lcm*aa[i]/GCD(aa[i],lcm);  
        }  
        for(int i=0;i<n;i++)  
            cin>>rr[i];  
        ll x0,y0;  
        bool flag=false;  
        for(int i=1;i<n;i++)  
        {  
            ll a=aa[0],b=aa[i],c=rr[i]-rr[0];  
            ll gcd=exgcd(a,x0,b,y0);  
            if(c%gcd!=0)  
            {  
                flag=true;  
                break;  
            }  
            ll MOD=b/gcd;  
            x0=(x0*c/gcd%MOD+MOD)%MOD;  
            rr[0]=aa[0]*x0+rr[0];  
            aa[0]*=(aa[i]/gcd);  
        }  
        printf("Case %d: ",++Case);  
        if(flag)  
            puts("-1");  
        else  
        {  
            if(rr[0]!=0)  
                cout<<rr[0]<<endl;  
            else  
                cout<<lcm<<endl;  
        }  
    }  
}  

 

补充：软件开发 , C++ ,