hdu 1573 X问题

 1 #include<cstdio>
 2 #define  scd(x)  scanf("%d",&x)
 3 #define  sclld(x)  scanf("%I64d",&x)
 4 #define  prd(x)  printf("%d\n",x)
 5 #define  For(i,s,t)  for(int i=s; i<t; ++i)
 6 typedef long long LL;
 7 
 8 LL gcd(LL a, LL b)    {    return b==0? a: gcd(b,a%b);     }
 9 LL lcm(LL x, LL y)    {    return x/gcd(x,y)*y;    }
10 
11 void gcd(LL a, LL b, LL &d, LL &x, LL &y){
12     if(!b)    {    d=a;  x=1;  y=0;    }
13     else   {    gcd(b,a%b,d,y,x);    y-= x*(a/b);    }
14 }
15 
16 LL inv(LL a, LL n){
17     LL d,x,y;
18     gcd(a,n,d,x,y);
19     return d==1? (x+n)%n:-1;
20 }
21 
22 bool merge(LL a1, LL n1, LL a2, LL n2, LL &aa, LL &nn){
23     LL d= gcd(n1,n2), c= a2-a1;
24     if(c%d)      return 0;
25     c= (c%n2+n2)%n2;
26     c/= d;
27     n2/= d;
28     c= c*inv(n1/d,n2)%n2;
29     c= c*n1+a1;
30     nn= n1*n2;
31     aa= (c%nn+nn)%nn;
32     return true;
33 }
34 
35 LL ext_china(LL len, LL a[], LL n[]){
36     LL a1= a[0], n1= n[0];
37     for(LL i=1; i<len; ++i){
38         LL aa, nn;
39         if(!merge(a1,n1,a[i],n[i],aa,nn))    return -1;
40         a1= aa;
41         n1= nn;
42     }
43     return (a1%n1+n1)%n1;
44 }
45 
46 LL a[12], b[12];
47 
48 int main(){
49     int t;
50     LL n,m,M;
51     scd(t);
52     while(t--){
53         sclld(n);    sclld(m);
54         M= 1;
55         For(i,0,m){
56             sclld(a[i]);
57             M= lcm(M,a[i]);
58         }
59         For(i,0,m)    sclld(b[i]);
60         LL tmp= ext_china(m,b,a);
61         if(tmp== -1){
62             puts("0");
63             continue;
64         }
65         int ans= 0;
66         while(tmp<=n){
67             if(tmp)      ++ans;
68             tmp+= M;
69         }
70         prd(ans);
71     }
72     return 0;
73 }