HDU 1573 X问题 （中国剩余定理解的个数）

明显是求中国剩余定理解的个数 。
中国剩余定理不太会用了，囧。。。。用三个等号表示同余
N===a1(mod r1)
N===a2(mod r2)
以两个为例，则x=a1+r1*x=a2+r2*y，根据后两者就可以建立方程  r1*x-r2*y=a2-a1，扩展欧几里德可搞。
解出x之后 可知N=a1+r1+x，明显这是其中一组解，N+K*（r1*r2）/gcd都是解。
如果有多个，则两两求，新的式子可以写成N===（a1+r1*x）（mod (r1*r2)/gcd）。
最终解出一个答案为b1,循环为a1
[cpp] 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<queue> 
#include<vector> 
#include<cmath> 
#define LL  long long 
#define MOD 1000000007 
#define eps 1e-6 
#define N 100010 
#define zero(a)  fabs(a)<eps 
using namespace std; 
LL extend_gcd(LL a,LL b,LL &x,LL &y){ 
    if(b==0){ 
        x=1; 
        y=0; 
        return a; 
    } 
    LL gcd=extend_gcd(b,a%b,x,y); 
    LL tmp=x; 
    x=y; 
    y=tmp-a/b*x; 
    return gcd; 
} 
int a[10],b[10]; 
int n,m; 
int main(){ 
    int t; 
    scanf("%d",&t); 
    while(t--){ 
        scanf("%d%d",&n,&m); 
        for(int i=0;i<m;i++) 
            scanf("%d",&a[i]); 
        for(int j=0;j<m;j++) 
            scanf("%d",&b[j]); 
        LL a1,a2,b1,b2,x,y; 
        bool flag=false; 
        a1=a[0];b1=b[0]; 
        for(int i=1;i<m;i++){ 
            a2=a[i];b2=b[i]; 
            LL gcd=extend_gcd(a1,a2,x,y); 
            if((b2-b1)%gcd){ 
                flag=true; 
                break; 
            } 
            LL t=a2/gcd; 
            x=(x*(b2-b1))/gcd; 
            x=(x%t+t)%t; 
            b1=a1*x+b1; 
            a1=(a1*a2)/gcd; 
            b1=(b1%a1+a1)%a1; 
        } 
        if(flag||n<b1) 
            printf("0/n"); 
        else www.2cto.com
            printf("%d/n",(n-b1)/a1+1-(b1==0?1:0)); 
    } 
    return 0; 
} 

作者：ACM_cxlove