ZOJ 3562 Alice's Sequence I 中国剩余定理 不互质
不互质的中国剩余定理
就不能直接方程组那样搞了
两个两个的搞就行
然后求出的解之间的间隔是固定的。
#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <algorithm>#include <cstdlib>#include <cmath>#include <map>#include <sstream>#include <queue>#include <vector>#define MAXN 111111#define MAXM 211111#define eps 1e-8#define INF 1000000001using namespace std;typedef long long LL;LL ExGcd(LL a, LL b, LL &x, LL &y){ if(b == 0) { x = 1; y = 0; return a; } LL r = ExGcd(b, a % b, x, y); LL t = x; x = y; y = t - a / b * y; return r;}LL a[111], m[111], l, r;int n;int main(){ while(scanf("%d", &n) != EOF) { LL M ; for(int i = 0; i < n; i++) scanf("%lld", &m[i]); int flag = 0; for(int i = 0; i < n; i++) scanf("%lld", &a[i]); for(int i = 0; i < n; i++) { if(a[i] >= m[i]) flag = 1; } scanf("%lld%lld", &l, &r); LL a1, b1, a2, b2; a1 = m[0], b1 = a[0]; for(int i = 1; i < n; i++) { a2 = m[i], b2 = a[i]; if(flag) continue; LL x, y; LL g = ExGcd(a1, a2, x, y); LL c = b2 - b1; if(c % g) { flag = 1; break; } LL tmp = a2 / g; c /= g; x = (x * c % tmp + tmp) % tmp; b1 = a1 * x + b1; a1 = a1 * tmp; } if(flag) printf("0\n"); else { LL now = b1 % a1; M = a1; if(l > now) { now = (l - now) / M * M + now; while(now < l) now += M; } LL cnt = 0; LL tmp = now; if(r >= now) cnt = (r - now) / M + 1; printf("%lld\n", cnt); if(cnt > 100) cnt = 100; int k = 0; now = tmp; while(now <= r) { k++; printf("%lld", now); if(k < cnt) printf(" "); else printf("\n"); if(k == cnt) break; now += M; } } } return 0;}