?
题意：求在小于等于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)。
思路：中国剩余定理的模板题，如果找不到这样的数或者最小的X大于N，输出零。
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #define PI acos(-1.0) #define maxn 10005 #define INF 0x7fffffff #define eps 1e-8 typedef long long LL; typedef unsigned long long ULL; using namespace std; LL MOD; LL extend_gcd(LL a, LL b, LL &x, LL &y) { if(b==0) { x=1; y=0; return a; } LL r=extend_gcd(b,a%b,x,y); LL t=x; x=y; y=t-a/b*y; return r; } LL inv(LL a,LL m) { LL d,x,y; d=extend_gcd(a,m,x,y); if (d==1) { x=(x%m+m)%m; return x; } else return -1; } LL gcd(LL a,LL b) { return b==0?a:gcd(b,a%b); } bool merge(LL a1,LL m1,LL a2,LL m2,LL &a3,LL &m3) { LL d=gcd(m1,m2); LL c=a2-a1; if(c%d) return false; c=(c%m2+m2)%m2; c/=d; m1/=d; m2/=d; c*=inv(m1,m2); c%=m2; c*=m1*d; c+=a1; m3=m1*m2*d; a3=(c%m3+m3)%m3; return true; } LL CRT_next(LL a[],LL m[],int n) { LL a1=a[0],m1=m[0],a2,m2; for(int i=1;i t1) printf(0 ); else printf(%I64d ,(t1-ans)/MOD+1); } } return 0; }