hdu 1573 X问题 (exgcd求解一般线性同余方程组解的个数)
题意：求在小于等于N的正整数中有多少个X满足：X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 10)。
思路：先用扩展欧几里得算法（excrt）解一般同余方程求出一个特解R,然后通解R' = R + k * LCM(a1..am)
注意一些特殊情况，如果无解输出0，如果n小于最小的正整数的R也输出0，
否则答案为(n-R)/M + 1
1/* ***********************************************
2Author :111qqz
3Created Time :Sat 15 Oct 2016 03:31:09 PM CST
4File Name :code/hdu/1573.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N =15;
32LL a[N],r[N];
33LL nn;
34int m;
35LL exgcd(LL a,LL b,LL &x,LL &y)
36{
37 if (b==0)
38 {
39 x = 1;
40 y = 0 ;
41 return a;
42 }
43 LL ret = exgcd( b, a%b,y,x);
44 y-=x*(a/b);
45 return ret;
46}
47LL ex_crt(LL *m,LL *r,int n)
48{
49 LL M = m[1] , R = r[1],x,y,gcd;
50 for ( int i = 2 ; i <= n ; i++)
51 {
52 gcd = exgcd(M,m[i],x,y);
53 if ((r[i]-R)%gcd) return 0;
54 LL gx = m[i]/gcd;
55 x = x*(r[i]-R)/gcd;
56 x %=gx;
57 R += x*M;
58 M = M / gcd * m[i];
59 R%=M;
60 }
61 if (R<=0) R+=M;
62 if (nn<R) return 0;
63 return (nn-R)/M + 1;
64}
65int main()
66{
67 #ifndef ONLINE_JUDGE
68 freopen("code/in.txt","r",stdin);
69 #endif
70 int T;
71 cin>>T;
72 while (T--)
73 {
74 scanf("%lld %d",&nn,&m);
75 for ( int i = 1 ; i <= m ; i++) scanf("%lld",&a[i]);
76 for ( int i = 1 ; i <= m ; i++) scanf("%lld",&r[i]);
77 LL res = ex_crt(a,r,m);
78 printf("%lld\n",res);
79 }
80 #ifndef ONLINE_JUDGE
81 fclose(stdin);
82 #endif
83 return 0;
84}