再谈数论

Loyal_Soldier · 2026-07-06 15:27:40 · 算法·理论

由于本人是小升区 xxs，数学学的不多，文章有错误还请多多谅解。

浅谈数论

由普及组二等小朋友变成了提高组三等小朋友 / 咦

使用 DeepSeek 优化了一下 Markdown。

二元一次不定方程

虽然是【模板】exgcd，但比 exgcd 难多了

对于不定方程 ax + by = c，求：

• 若该方程有整数解，且有正整数解，求正整数解的数量、正整数解中 x 的最小值、正整数解中 y 的最小值、正整数解中 x 的最大值、正整数解中 y 的最大值。
• 若该方程有整数解，没有正整数解，求整数解中 x 的最小正整数值、y 的最小正整数值。

显然，根据裴蜀定理，如果 \gcd(a, b) \nmid c，则方程无解。

::::info[裴蜀定理] 设 a, b 是不全为零的整数，那么，对于任意整数 x, y，都有 \gcd(a, b) \mid ax+by 成立，并且，存在整数 x, y，使得 ax + by = \gcd(a, b) 成立。

:::info[证明] 设 d = \gcd(a, b)。因为 d \mid a, b，所以存在整数 p, q，使得 a = pd, b = qd 成立，因此，总有：

说明 d \mid ax + by。

考虑 a, b 都 \ne 0 的情况，如果 a 或 b 是 0，显然有 (x, y) = (1, 0)/(0, 1) 使得 ax + by = \gcd(a, b) 成立。

因为 \gcd(a, b) = \gcd(-a, b) = \gcd(a, -b)，设 a, b > 0。

考虑辗转相除：

因为最大公因数是 d，所以 r_n = d，根据倒数第二个等式，那么：

根据倒数第三个等式：

带入上式：

以此类推，逐步消去 r_{n - 2}, r_{n - 3}, \dots，可以得到：

证毕。 ::: ::::

首先，使用 exgcd 求出 ax + by = \gcd(a, b) 的解，记为 x_0, y_0，则有：

显然，我们找到了原方程的一组特解 x_1 = \frac{x_0c}{\gcd(a, b)}, y_1 = \frac{y_0c}{\gcd(a, b)}。

我们设 a(x_1 + m) + b(y_1 + n) = c，考虑怎么求出 m, n。

将式子展开可以发现，需要让 am + bn = 0。

我们让 m = t \times \frac{b}{\gcd(a, b)}, n = t \times \frac{a}{\gcd(a, b)}(t \in \mathbb{Z})，带入发现 am + bn = 0，于是通解为：

x 最小值

显然，我们要找出最小的 t 使得 x \ge 1。

显然可以直接求。

y 最大值

根据 ax + by = c，可得 y = \frac{c - ax}{b}。

注意到 y 在 \mathbb{R} 上单调递减，x 取到 x_{\min} 再求出 y_{\max} 即可。

如果 y_{\max} \le 0，就没有正整数解。

y 最小值

考虑 ax_{\max} + by_{\min} = c 这个方程。

由于 ax_{\min} + by_{\max} = c，设 \Delta x = x_{\max} - x_{\min}, \Delta y = y_{\min} - y_{\max}。

得：

根据

说明

由于 y_{\min} 必须是最小正整数，得：

x 最大值

和 y_{\max} 一样，把 y_{\min} 代入即可。

解的个数

我们在 (y_{\min}, y_{\max}] 中寻找解。

考虑变换一下通解格式：

显然，每隔 \frac{a}{\gcd(a, b)} 个就会存在一个解，那么解的个数为 \frac{y_{\max} - y_{\min}}{\frac{a}{\gcd(a, b)}} + 1。

对于正无整数解的情况，也是类似的。

::::success[code]

while (T--) {
    int a, b, c;
    cin >> a >> b >> c;
    exgcd(a, b);
    int qwq = __gcd(a, b);
    if (c % qwq) {
        cout << "-1\n";
        continue;
    }
    x = x * c / qwq;
    y = y * c / qwq;
    int X = b / qwq, Y = a / qwq;
    int awa = ceil((1.0 - x) / X);
    x += X * awa;
    y -= Y * awa;
    if (y <= 0) {
        int y_min = y + Y * ceil((1.0 - y) / Y);
        cout << x << ' ' << y_min << '\n';
    }
    else cout << (y - 1) / Y + 1 << ' ' << x << ' ' << (y - 1) % Y + 1 << ' ' << x + (y - 1) / Y * X << ' ' << y << '\n';
}

::::

推荐习题

• P3409
• P3986
• P2421

Lucas 定理

对于 p 是质数，有 \binom{n}{m} = \binom{\left\lfloor \frac{n}{p} \right\rfloor}{\left\lfloor \frac{m}{p} \right\rfloor} \binom{n \bmod p}{m \bmod p} \pmod p。

:::::info[证明]{open} ::::info[引理] 对于质数 p 和整数 x，有 (1 + x)^p \equiv 1 + x^p \pmod p。

:::info[引理的证明] 由二项式定理可得 (1 + x)^p = \sum_{k = 0}^p \binom{p}{k} x^k。 当 0 < k < p 时，显然 \binom{p}{k} 可以被 p 整除，那么 (1 + x)^p \equiv 1 + x^p \pmod p。 ::: ::::

考虑将 n, m 变一下形式

考虑将 (1 + x)^n 展开，得到 (1 + x)^n = (1 + x)^{sp + q} = ((1 + x)^p)^s (1 + x)^q。

将 (1 + x)^q 带入引理，可得：

我们来比较两边 x^m 的项数。

左边：(1 + x)^n = \sum_{k = 0}^n \binom{n}{k} x^k，则 x^m 的系数就是 \binom{n}{m}。

右边：

• 将第一项展开 (1 + x^p)^s = \sum_{t = 0}^s \binom{s}{t} x^{tp}
• 将第二项展开 (1 + x)^q = \sum_{r = 0}^q \binom{q}{r} x^r

某一项指数为 tp + r，注意到 m = tp + r 这一种表示方法是唯一的，所以右边系数只能是 \binom{s}{t} \binom{q}{r}。

可得 \binom{n}{m} = \binom{s}{t} \binom{q}{r}，转变一下形式就是：

证毕。 :::::

::::success[code]

int C(int n, int k, int mod) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv[k] % mod * inv[n - k] % mod;
}
int Lucas(int n, int k, int mod) {
    if (k == 0) return 1;
    return C(n % mod, k % mod, mod) * Lucas(n / mod, k / mod, mod) % mod;
}

::::

例题 P2480

数论大杂烩

给一个整数 n，求：

g^{\sum_{d \mid n} \binom{n}{d}} \bmod 999911659

如果 999911659 \mid g，答案就是 0。

注意到模数 999911659 是一个质数，考虑对其使用费马小定理。

::::::info[费马小定理] 若整数 p 为质数且 p 与整数 a 互质，则满足：

:::::info[证明] 因为 p 是质数，那么 \varphi(p) = p - 1，这时就转化成了欧拉定理的一种情况，由于满足欧拉定理，费马小定理一定成立。

::::info[欧拉定理] 若正整数 a, n 互质，则：

其中 \varphi(n) 为欧拉函数，表示 1 \sim n 中与 n 互质的数的个数。

:::info[证明] 设 x_1, x_2, \dots, x_{\varphi(n)} 为 1 \sim n 中与 n 互质的数。

这时，我们发现 a \times x_1, a \times x_2, \dots, a \times x_{\varphi(n)} 具有这个性质：每个数 \bmod n 两两不同，且余数与 n 互质。而且，x_1, x_2, \dots, x_{\varphi(n)} 也具有这个性质。

有了这个性质，将 a \times x_1, a \times x_2, \dots, a \times x_{\varphi(n)} 都 \bmod n 后一定是 \varphi(n) 个不同的与 n 互质的数，那么：

::: :::: ::::: ::::::

然后，原式变成了：

考虑怎么求 \sum_{d \mid n} \binom{n}{d} \bmod 999911658。