?

題意有個大小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\n", lcm);
50 //    printf("CRT: %lld %lld\n", 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 }

?

轉載于:https://www.cnblogs.com/xFANx/p/9447743.html

總結

以上是生活随笔為你收集整理的Codeforces 338D 对线性同余方程组的一点理解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。