hdu1573 X问题（中国剩余定理 不互质）

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1573

思路：就是让你通过中国剩余定理求解出多组解，然后求出满足条件的正整数解有多少个。

正整数解=x0+lcm*k（x0最小正整数解，k任意非负整数）

坑点：1.wtf理论了解不是很透彻，原来中国剩余定理是有0解的！！

  2.当解为负数解的时候，你要通过lcm将他调整为最小正整数解。

  3.正整数！！！！0不是正整数。

  4.lcm要求，我的最开始写的模板没有lcm的求解。lcm(a,b)=a*b/gcd(a,b);

  5.long long 数据类型，n不用。

总结：疯狂wrong，我靠差点受不了。不断地改啊改，终于成功了。

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
const int maxn=12;
ll mod;
int n;
ll lcm;
int flag;
ll a[maxn],m[maxn];//m为mod数组，a为余数数组

ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(b==0){
        x=1,y=0;
        return a;
    }
    ll ans=exgcd(b,a%b,x,y);
    ll temp=x;
    x=y;
    y=temp-a/b*y;
    return ans;
}
ll Gcd(ll a,ll b)
{
    if(b==0) return a;
    return Gcd(b,a%b);
}
int china2(int num){//不互质的中国剩余定理
    ll m1=m[0],a1=a[0],m2,a2,k1,k2,x0,gcd,c;
    lcm=m[0];
    for(int i=1;i<num;i++){
        m2=m[i],a2=a[i];
        c=a2-a1;
        gcd=exgcd(m1,m2,k1,k2);//解得：n1*k1+n2*k2=gcd(n1,n2)
        lcm=lcm*m[i]/Gcd(lcm,m[i]);
        if(c%gcd){
            flag=1;
            return 0;//无解
        }
        x0=c/gcd*k1;//n1*x0+n2*(c/gcd*k2)=c  PS:k1/gcd*c错误！
        ll t=m2/gcd;
        x0=(x0%t+t)%t;//求n1*x0+n2*y=c的x0的最小解
        a1+=m1*x0;
        m1=m2/gcd*m1;
    }
    return a1;
}

int main()
{
    int T;scanf("%d",&T);while(T--){
        scanf("%lld%d",&mod,&n);
        for(int i=0;i<n;i++) scanf("%lld",&m[i]);
        for(int i=0;i<n;i++) scanf("%lld",&a[i]);
        flag=0;
        ll ans=china2(n);
        int sum=0;
        if(flag==1||mod<ans) printf("0\n");//中国剩余定理解出来的值可能为0可能为负值可能为正，所以要加flag判断无解
        else{
            while(ans<=0) ans+=lcm;//题目要求是正整数，所以要通过最小公倍数将负数不断变为正整数
            while(ans<=mod){//计算正解的个数
                sum++;
                ans+=lcm;
            }
            printf("%d\n",sum);
        }
    }
}