题解 | #GCD Table#

【GCD Table】 若选中的起始位置为$(i,j)(i,j)$(i,j)​，则：

上式可以通过excrt求得$jj$j​​​​​的通解：$j=j_0+M\cdot x,M=lcm(a_1,a_2...a_k)j=j\_0+M\backslash cdot\; x,\backslash \; M=lcm(a\_1,a\_2...a\_k)$j=j0​+M⋅x, M=lcm(a1​,a2​...ak​)​​​，且$ii$i​​​​​​​​​是$MM$M​​​​​​​​​​​的倍数，$i=M+M\cdot yi=M+M\backslash cdot\; y$i=M+M⋅y。

若$g=gcd(M,j_0)g=gcd(M,j\_0)$g=gcd(M,j0​)​，$g^{\prime }=gcd(M+M\cdot y,j_0+M\cdot x)g\text{'}=gcd(M+M\backslash cdot\; y,j\_0+M\backslash cdot\; x)$g′=gcd(M+M⋅y,j0​+M⋅x)​，可以看出$g\mid g^{\prime }g|g\text{'}$g∣g′。

只需要判断$j=j_0,i=Mj=j\_0,i=M$j=j0​,i=M​是否成立就行了，因为$gcd(i,j+t)gcd(i,j+t)$gcd(i,j+t)有可能是$a_{t+1}a\_\{t+1\}$at+1​​​​​的倍数，这样条件就不成立。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e4 + 10;

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int nx, ny;
    int d = exgcd(b, a % b, nx, ny);
    x = ny;
    y = nx - a / b * ny;
    return d;
}

int lcm(int a, int b) { return a / __gcd(a, b) * b; }

pair<int, int> excrt(int k, int *a, int *r) {
    int M = r[1], ans = a[1];
    for (int i = 2; i <= k; i++) {
        int x0, y0;
        int c = a[i] - ans;
        int g = exgcd(M, r[i], x0, y0);
        if (c % g != 0) return {-1, -1};
        x0 = (__int128)x0 * (c / g) % (r[i] / g);
        ans = x0 * M + ans;
        M = lcm(M, r[i]);
        ans = (ans % M + M) % M;
    }
    return {ans, M};
}

int n, m, k, a[N];
int b[N];
signed main() {
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) cin >> a[i], b[i] = -(i - 1);

    pair<int, int> x = excrt(k, b, a);
    if (x.first == 0) x.first = x.second;

    if (x.first > m - k + 1 || x.second > n || x.first == -1) {
        cout << "NO";
    } else {
        for (int i = 0; i < k; i++)
            if (__gcd(x.first + i, x.second) != a[i + 1]) {
                cout << "NO";
                return 0;
            }
        cout << "YES";
    }
    return 0;
}