題意：求在小於等於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;it1) printf(0 ); else printf(%I64d ,(t1-ans)/MOD+1); } } return 0; }
一個基本問題引出的話題，類常識你知多少？，引出的話題類常識以
POJ 2955 Brackets，poj2955brack
雙重檢查鎖定模式(DCLP)在無鎖編程(lock-free
HDU 5078-Osu!（簽到） Osu! Time
快排序算法，排序算法快速排序是由東尼·霍爾所發
程序基石:C++多態的前提條件 准備知識C++中多態(p
