Codeforces 338D 对线性同余方程组的一点理解

题意有个大小n*m（两个数都不大于10的12次幂）的表格，table[i][j]的值为gcd(i, j)。给出k（<=10000)个数

判断这个序列是否在表格中的某一列出现过

考虑解满足的条件

显然行必须为序列中所有数的倍数，那么我们先考虑最小公倍数

此时对于列，有

y % a1 == 0;

(y + 1) % a2 == 0;

...

(y + k - 1) % ak == 0;

那么我们可以求解线性同余方程组，得到一个最小的满足条件的y（或无解）

有解的情况下，我们还需要检验对应位置是否有table[x][y] == gcd(x, y)

那如果检验结果为假呢，我们要怎么考虑改变x或y去获得答案呢

由于特别的，每个方程的变量y的系数都为1，那么最终得到答案形式中y≡b(mod m) 中的m必然为序列a的最小公倍数。

考虑只不改变行，只改变列的起始位置是否有解呢？不行，因为为了满足方程组的解，新的y必然与当前y相差m（也等同与最小公倍数）的整数倍，

根据辗转相处法我们知道gcd(x, y) == gcd(x, y + x);

考虑只改变行，不改变列呢。答案也是否定的，因为如果改变某位置的gcd变为k倍，那么之前的行必然不是a序列的最小公倍数（反证即可）

最后同时增加行和列的情况，可以逐步转为到只增加行或列的情况，所以也无需判断

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 const int maxn = 1e4 + 10;
 7 
 8 LL M[maxn];
 9 LL n, m, k;
10 LL lcm;
11 
12 LL gcd(LL x, LL y) {return y == 0 ? x : gcd(y, x % y);}
13 
14 LL extgcd(LL a, LL b, LL &x, LL &y) {
15     LL d = a;
16     if (b) {
17         extgcd(b, a % b, y, x);
18         y -= (a / b) * x;
19     } else {
20         x = 1; y = 0;
21     }
22     return d;
23 }
24 
25 LL mod_inverse(LL a, LL m) {
26     LL x, y;
27     extgcd(a, m, x, y);
28     return (m + x % m) % m;
29 }
30 
31 pair<LL, LL> LC(LL M[]) {
32     LL x = 0, m = 1;
33     for (int i = 0; i < k; i++) {
34         LL a = m;
35         LL b = (-i) - x;
36         LL d = gcd(M[i], a);
37         if (b % d != 0) return make_pair(LL(-1), -1);
38         LL t = b / d * mod_inverse(a / d, M[i] / d) % (M[i] / d);
39         x = x + m * t;
40         m *= M[i] / d;
41     }
42     return make_pair((m + x % m) % m, m);
43 }
44 
45 bool solve() {
46     pair<LL, LL> P = LC(M);
47     LL res = P.first;
48 
49 //    printf("lcm: %lld
", lcm);
50 //    printf("CRT: %lld %lld
", P.first, P.second);
51 
52     if (res == 0) res += P.second;
53     if (res < 0 || res + k - 1 > m) {
54         return false;
55     }
56     bool flag = true;
57     for (int i = 0; i < k && flag; i++) {
58         if (gcd(lcm, res + i) != M[i]) flag = false;
59     }
60     return flag;
61 }
62 
63 int main() {
64     
65     scanf("%lld%lld%lld", &n, &m, &k);
66     lcm = 1;
67     for (int i = 0; i < k; i++) {
68         scanf("%lld", &M[i]);
69         lcm = lcm / gcd(lcm, M[i]) * M[i];
70     }
71     if (lcm > n) {
72         puts("NO");
73     } else {
74         if (solve()) {
75             puts("YES");
76         } else {
77             puts("NO");
78         }
79     }
80     return 0;
81 }