题目链接：
?pid=1573
题目大意：
求在小于等于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)。
思路：
先求出数组b[]中所有数的最小公倍数lcm，再求解出该一元线性同余方程组在lcm范围内的解为a，题目要
求解x是小于等于N的正整数，则可列不等式：a + lcm * x <= N。那么，如果a = 0，则答案为x-1，，如果
a != 0，则答案为x。
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;__int64 GCD(__int64 a,__int64 b){if(b == 0)return a;elsereturn GCD(b,a%b);}void ExGCD(__int64 a,__int64 b,__int64 &d,__int64 &x,__int64 &y){if( !b ){x = 1;y = 0;d = a;}else{ExGCD(b,a%b,d,y,x);y -= x * (a/b);}}__int64 A[15],B[15];int main(){int T,N,M;__int64 a,b,c,d,x0,y0,lcm;cin >> T;while(T–){cin >> N >> M;bool flag = 1;lcm = 1;for(int i = 1; i <= M; ++i){cin >> A[i];lcm = lcm / GCD(lcm,A[i]) * A[i];}for(int i = 1; i <= M; ++i)cin >> B[i];for(int i = 2; i <= M; ++i){a = A[1];b = A[i];c = B[i] – B[1];ExGCD(a,b,d,x0,y0);if(c % d != 0){flag = 0;break;}__int64 temp = b / d;x0 = (x0*(c/d)%temp + temp) % temp;B[1] = A[1] * x0 + B[1];A[1] = A[1] * (A[i]/d);}if( !flag ){cout << "0" << endl;continue;}__int64 Ans = 0;if(B[1] <= N)Ans = 1 + (N – B[1])/lcm;if(Ans && B[1] == 0)Ans–;cout << Ans << endl;}return 0;}
只要有信心，人永远不会挫败
