「Codeforces 338D」GCD Table

Description

给定一个 $n \times m\ (1 \leq n,m \leq 10^{12})$ 的表 格，其中 第 $i$ 行，第 $j$ 列 的元素是 $\gcd(i,j)$ 。现在有一个长度为 $k\ (1\leq k \leq 10^4)$ 的序列 $a\ (1 \leq a_i \leq 10^{12})$，询问在表格内是否存在

$x,y\ (1 \leq x \leq n,1 \leq y \leq m - k +1)$，满足对于任意一个 $l$，

都有 $\gcd(x,y+l-1) = a_l\ (1 \leq l \leq k)$（即这个序列在表格的某一行中出现过）。

Source

[Luogu]CF338D

[Codeforces]338D

Solution

前置知识：

扩展中国剩余定理(exCRT)

由题意得

$$\left\{\begin{matrix} \begin{aligned} \gcd(x,y)&=a_1\\[1ex] \gcd(x,y+1)&=a_2\\[1ex] \gcd(x,y+2)&=a_3\\[1ex] &\cdots\\[1ex] \gcd(x,y + k - 1) &= a_k \end{aligned} \end{matrix}\right.$$

显然对于所有的 $a_i\ (1 \leq i \leq k)$ 都满足 $a_i \mid x$，所以 ${\rm lcm}\begin{Bmatrix}a_1,a_2,a_3,\ldots,a_k\end{Bmatrix} \mid x$ 。假设 $x = k \times lcm$（$k$ 是正整数），那么 $\gcd(k \times lcm,y+i-1) = a_i$，也就是说要限制 $\gcd\left( k \times \frac{lcm}{a_i},\frac{y+i-1}{a_i} \right) = 1$ 。取 $k = 1$ 时，对该式子的影响最小，由此能够得到 $x={\rm lcm}\begin{Bmatrix}a_1,a_2,a_3,\ldots,a_k\end{Bmatrix}$ 。

至于 $y$ 呢？由上述方程组能够得到

$$\left\{\begin{matrix} \begin{aligned} a_1 &\mid y\\[1ex] a_2 &\mid y + 1\\[1ex] a_3 &\mid y + 2\\[1ex] &\cdots\\[1ex] a_k &\mid y + k - 1 \end{aligned} \end{matrix}\right.\\[10ex] \Leftrightarrow \left\{\begin{matrix} \begin{aligned} y &\equiv 0 \pmod {a_1}\\[1ex] y + 1 &\equiv 0 \pmod {a_2}\\[1ex] y + 2 &\equiv 0 \pmod {a_3}\\[1ex] &\cdots\\[1ex] y + k-1&\equiv 0 \pmod {a_k} \end{aligned} \end{matrix}\right.$$

根据同余式的性质，化简该方程组，得到

$$\left\{\begin{matrix} \begin{aligned} y &\equiv 0 \pmod {a_1}\\[1ex] y &\equiv -1 \pmod {a_2}\\[1ex] y &\equiv -2 \pmod {a_3}\\[1ex] &\cdots\\[1ex] y &\equiv 1-k \pmod {a_k} \end{aligned} \end{matrix}\right.$$

这是一个线性同余方程组，且模数不一定两两互质，所以能用 扩展中国剩余定理(exCRT) 求出 $y$ 的最小正整数解。

难道只需要考虑 $y$ 的最小正整数解吗？实际上 $y + k \times {\rm lcm}\begin{Bmatrix}a_1,a_2,a_3,\ldots,a_k\end{Bmatrix}$ 都是这个方程组的解，但因为 $\gcd(lcm, y) = \gcd(lcm,y + lcm) =\gcd(lcm,y +k\times lcm)$（原理：更相减损法），所以没必要尝试。

求出了 $x$ 和 $y$ 还没有结束，因为只满足 $a_i \mid x$ 和 $a_i \mid y + i -1\ (1 \leq i \leq k)$，可能会出现 $\gcd(x,y+i-1)\neq a_i$（即 $\gcd \left( \frac{x}{a_i},\frac{y+i-1}{a_i} \right) \neq 1$）的情况，所以要验证该解是否成立。总时间复杂度为 $O(k \log a_i)$ 。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
	int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 1e4;
int k;
LL ans, n, m, a[MAXN + 5], b[MAXN + 5];

inline LL slowMul(LL x, LL p, LL mod) {
    LL res = 0;
    for (; p; p >>= 1, x = (x + x) % mod)
        if (p & 1)
            res = (res + x) % mod;
    return res;
}

LL gcd(LL a, LL b) { return !b ? a : gcd(b, a % b); }

LL exGcd(LL a, LL b, LL &x, LL &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    LL d = exGcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

inline LL exCrt(LL *a, LL *b, LL &lcm) {//求解 ans ≡ a[i] (mod b[i])
    LL res = a[1];
    lcm = b[1];//第一个方程的解 
    for (int i = 2; i <= k; ++i) {
        LL x, y, c = ((a[i] - res) % b[i] + b[i]) % b[i], d = exGcd(lcm, b[i], x, y), m = b[i] / d;
        if (c % d) return -1;//无解
        x = slowMul(x, c / d, m);
        res += lcm * x;
        lcm *= m;
        if (lcm > n) return -1;//如果 lcm{a[i]} 比 n 大，肯定找不到合适的 x 满足题意 
        res = (res + lcm) % lcm;
    }
    return res == 0 ? lcm : res;//y 的值不能为 0，所以最小正整数解为 lcm
}

int main() {
    read(n), read(m), read(k);
    for (int i = 1; i <= k; ++i) {
        read(a[i]);
        b[i] = ((1 - i) % a[i] + a[i]) % a[i];
    }//y ≡ 1 - i (mod a[i])
    LL x, y = exCrt(b, a, x);//同余的数是 b[i]，模数是 a[i] 
    if (y == -1 || y > m - k + 1) {//y 无解 或 超出表格 
        puts("NO");
        return 0;
    }
    for (int i = 1; i <= k; ++i)
        if (gcd(x, y + i - 1) != a[i]) {
            puts("NO");
            return 0;
        }//验证该解是否成立 
    puts("YES");
    return 0;
}