不互质的中国剩余定理
就不能直接方程组那样搞了
两个两个的搞就行
然后求出的解之间的间隔是固定的。
#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 1000000001
using 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;
}