HDU3579 Hello Kiki 解线性同余方程的应用 - c++编程基础

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

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

估计没少有人被坑吧

 
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
  
#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 > G;  
//typedef pair P;  
//vector> ::iterator iter;  
//  
//mapmp;  
//map::iterator p;  
//  
//vectorG[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>aa[i];  
            lcm=lcm*aa[i]/GCD(aa[i],lcm);  
        }  
        for(int i=0;i>rr[i];  
        ll x0,y0;  
        bool flag=false;  
        for(int i=1;i