一些数论算法及证明

发表于 2024-01-25 更新于 2026-02-06 分类于算法竞赛，数论

辗转相除法

等式 1 如果 $a\mid b$ 且 $b\mid a$，那么 $a=b$

等式 2 如果 $d\mid a$ 且 $d\mid b$ 那么 $d\mid(ax + by);x,y \in Z$

等式 3 $a\bmod\ n = a - n\left \lfloor\frac{a}{n}\right \rfloor;a\in Z,n\in N^{*}$

推论 1 对任意整数 $a$, $b$，如果 $d\mid a$ 且 $d\mid b$ 则 $d\mid\gcd(a, b)$

如果我们想要获得结论 $\gcd(a,b) = \gcd(b,a\bmod\ b)$

那么我们只需要证明 $\gcd(a,b)\mid\gcd(b,a\bmod b)$ 且 $\gcd(b,a\bmod b)\mid\gcd(a,b)$ 就可以来证明它俩相等了。

证明 $\gcd(a,b)\mid\gcd(b,a\bmod b)$

设 $d = \gcd(a, b)$ $\therefore d\mid a$ 且 $d\mid b$。
由 等式 3 可知：$a\pmod b = a - qb,q = \left \lfloor\frac{a}{b}\right \rfloor$
$\therefore a\bmod\ b$ 是 a 与 b 的线性组合
由 等式 2 可知：$d\mid a\pmod b$
$\because d\mid b$ 且 $d\mid a\pmod b$
$\therefore$ 由 推论 1 可知 $d\mid\gcd(b, a\bmod\ b)$
等价结论： $\gcd(a, b)\mid\gcd(b, a\bmod\ b)$

证明 $\gcd(b,a\bmod\ b)\mid\gcd(a,b)$

设 $c = \gcd(b, a\bmod\ b)$
$\therefore c\mid b$ 且 $c\mid a\pmod b$
$\because a = qb + r,r = a\bmod\ b,q = \left \lfloor\frac{a}{b}\right \rfloor$
$\therefore a$ 是 $b$ 和 $a\bmod\ b$ 的线性组合
由 等式 2 可知：$c\mid a$
$\because c\mid a$ 且 $c\mid b$
由 推论 1 可知：$c\mid\gcd(a, b)$
等价结论： $\gcd(b, a\bmod\ b)\mid\gcd(a, b)$

证明 $\gcd(a,b) = \gcd(b, a\bmod b)$

由上述两个结论可知： \[ \begin{aligned} \gcd(a, b)\mid\gcd(b, a\bmod\ b)\\ \gcd(b, a\bmod\ b)\mid\gcd(a, b) \end{aligned} \] 由 等式 1 可知：$\gcd(a, b) = \gcd(b, a\bmod\ b)$

扩展欧几里得算法

求 $ax+by=gcd(a,b)$

设

\[ \begin{aligned} ax_1+by_1&=\gcd(a,b) \\ bx_2+(a\bmod b)y_2&=\gcd(b,a\bmod b) \end{aligned} \]

由欧几里得定理可知：$\gcd(a,b)=\gcd(b,a\bmod b)$

所以 $ax_1+by_1=bx_2+(a\bmod b)y_2$

又因为 $a\bmod b=a-\lfloor\frac{a}{b}\rfloor\times b$

所以 \[ ax_1+by_1=bx_2+(a-\lfloor\frac{a}{b}\rfloor\times b)y_2 \] $ax_1+by_1=ay_2+bx_2-\lfloor\frac{a}{b}\rfloor\times by_2=ay_2+b(x_2-\lfloor\frac{a}{b}\rfloor y_2)$

$a,b$ 相同，所以 $x_1=y_2,y_1=x_2-\lfloor\frac{a}{b}\rfloor y_2$

将 $x_2,y_2$ 不断代入递归求解直至 $\gcd$（最大公约数，下同）为 0 递归 x=1,y=0 回去求解。

code

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

同余方程

求关于 $ x$ 的同余方程 $ a x b$ 的最小正整数解。

对于 $100\%$ 的数据，$2\le a, b\le 2,000,000,000$。

solution

$ax\bmod\ b=1$ 实质是 $ax+by=1$。 $y$ 是我们引入的某个整数，这里似乎是个负数。

扩展欧几里得求 $ax+by=\gcd(a,b)$，所以这里 $\gcd(a,b)=1$，即 $a$，$b$ 互质。所以 $a$ 有模 $b$ 下的乘法逆元的条件为 $a$，$b$ 互质。

我们将要求出来的 $x$， $y$ 仅仅保证满足 $ax+by=1$，而 $x$ 不一定是最小正整数解。有可能太大，也有可能是负数。$x$ 批量的减去或加上 $b$，能保证 $ax+by=1$。因为： \[ a(x+kb)+b(y-ka)=1 \] 这里我们可以这么写

1	x = (x % b + b) % b

二元一次不定方程

P5656 【模板】二元一次不定方程 (exgcd) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

\[ ax+by=c \]

$\gcd(a,b)\mid(ax+by)$，若 $c$ 不是 $\gcd(a,b)$ 的倍数直接无解

记 $ax+by=\gcd(a,b)$ 的一组特解为 $x_0$，$y_0$。则有:

\[ \begin{aligned} ax_0+by_0=\gcd(a,b) \\ a\frac{x_0c}{\gcd(a,b)}+b\frac{y_0c}{\gcd(a,b)}=c \end{aligned} \]

故我们已经找到原方程的一组整数特解，记为 $x_1$ 和 $y_1$

\[ \begin{aligned} x_1=\frac{x_0c}{\gcd(a,b)}, \quad y_1=\frac{y_0c}{\gcd(a,b)} \end{aligned} \]

那么我们考虑构造原方程整数通解形式

我们设任意 $d\in Q$，那么必有 \[ a(x_1+db)+b(y_1-da)=c \] 显然对于最小的 $db$，$da$，$d=\frac{1}{\gcd(a,b)}$

然后像上面一样开始乱搞

int d = exgcd(a, b, x, y);
if(c % d) {
    cout << -1 << endl;
    return;
}
x = c * x / d, y = c * y / d;
int dx = b / d, dy = a / d;
int minx = (x % dx + dx) % dx;
if(minx == 0) minx = dx;
int maxy = (c - a * minx) / b;
int miny = (y % dy + dy) % dy;
if(miny == 0) miny = dy;
int maxx = (c - b * miny) / a;

中国剩余定理

模数不互质的情况

设两个方程分别是 $x\equiv a_1\pmod m_1,x\equiv a_2\pmod m_2$

将它们转化为不定方程：$x=m_1p+a_1=m_2q+a_2$，其中 $p, q$ 是整数，则有 $m_1p-m_2q=a_2-a_1$。

由裴属定理，当 $a_2-a_1$ 不能被 $\gcd(m_1,m_2)$ 整除时，无解；

其他情况下，可以通过扩展欧几里得算法解出来一组可行解 $(p,q)$；

则原来的两方程组的模方程组的解为 $x\equiv b\pmod M$，其中 $b=m_1p+a_1$, $M=\mathrm{lcm}(m_1,m_2)$。

Lucas 定理

对于质数 $p$，有

\[ \binom{n}{m}\bmod p=\binom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor}\cdot\binom{n\bmod p}{m\bmod p}\bmod p \]

观察上述表达式，可知 $n\bmod p$ 和 $m\bmod p$ 一定是小于 $p$ 的数，可以直接求解，$\displaystyle\binom{\left\lfloor\frac{n}{p}\right\rfloor}{\left\lfloor\frac{m}{p}\right\rfloor}$ 可以继续用 Lucas 定理求解。这也就要求 $p$ 的范围不能够太大，一般在 $10^5$ 左右。边界条件：当 $m=0$ 的时候，返回 $1$。

证明

考虑 $\displaystyle\binom{p}{n} \bmod p$ 的取值，注意到 $\displaystyle\binom{p}{n} = \frac{p!}{n!(p-n)!}$，分子的质因子分解中 $p$ 的次数恰好为 $1$，因此只有当 $n = 0$ 或 $n = p$ 的时候 $n!(p-n)!$ 的质因子分解中含有 $p$，因此 $\displaystyle\binom{p}{n} \bmod p = [n = 0 \vee n = p]$。进而我们可以得出:

\[ \begin{align} (a+b)^p &= \sum_{n=0}^p \binom pn a^n b^{p-n}\\ &\equiv \sum_{n=0}^p [n=0\vee n=p] a^n b^{p-n}\\ &\equiv a^p + b^p \pmod p \end{align} \]

注意过程中没有用到费马小定理，因此这一推导不仅适用于整数，亦适用于多项式。因此我们可以考虑二项式 $f^p(x)=(ax^n + bx^m)^p \bmod p$ 的结果

\[ \begin{align} (ax^n + bx^m)^p &\equiv a^p x^{pn} + b^p x^{pm} \\ &\equiv ax^{pn} + bx^{pm}\\ &\equiv f(x^p) \end{align} \]

note: $a^{p-1}\equiv 1\pmod{p}$

考虑二项式 $(1+x)^n \bmod p$，那么 $\displaystyle\binom n m$ 就是求其在 $x^m$ 次项的取值。使用上述引理，我们可以得到

\[ \begin{align} (1+x)^n &\equiv (1+x)^{p\lfloor n/p \rfloor} (1+x)^{n\bmod p}\\ &\equiv (1+x^p)^{\lfloor n/p \rfloor} (1+x)^{n\bmod p} \end{align} \]

注意前者只有在 $p$ 的倍数位置才有取值，而后者最高次项为 $n\bmod p \le p-1$，因此这两部分的卷积在任何一个位置只有最多一种方式贡献取值，即在前者部分取 $p$ 的倍数次项，后者部分取剩余项，即

\[ \displaystyle\binom{n}{m}\bmod p = \binom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p\right\rfloor}\cdot\binom{n\bmod p}{m\bmod p}\bmod p \]

扩展 Lucas定理

求

\[ {\mathrm{C}}_n^m \bmod{p} \]

其中 $p\le 10^6$，不保证 $p$ 为质数。

证明

扩展Lucas定理 - HorizonWind 的洛谷博客

莫比乌斯反演

若 $f$ 是算数函数，$F$ 为 $f$ 的和函数，对任意正整数 $n$，满足 $F(n)=\sum_{d\mid n}f(d)$，则有 $f(n)=\sum_{d\mid n}\mu(d)F(\frac{n}{d})$

证明：

$i\mid\frac{n}{d}\iff id\mid n\iff d\mid \frac{n}{i}$

\[ \begin{align} \sum_{d\mid n}\mu(d)F(\frac{n}{d})&=\sum_{d\mid n}\mu(d)\sum_{i\mid\frac{n}{d}}f(i) \\ &=\sum_{i\mid n}f(i)\sum_{d\mid\frac{n}{i}}\mu(d) \end{align} \]

当 $\frac{n}{i}$ 为 $1$ 的时候，$\sum_{d\mid\frac{n}{i}}\mu(d)=1$，其它均为 $0$。

所以

\[ \sum_{d\mid n}\mu(d)F(\frac{n}{d})=f(n) \]

若 $F(n)=\sum_{n\mid d}f(d)$，则 $f(n)=\sum_{n\mid d}\mu(\frac{d}{n})F(d)$

证明： \[ \sum_{n\mid d}\mu(\frac{d}{n})F(d)=\sum_{n\mid d}\mu(\frac{d}{n})\sum_{d\mid i}f(i) \] $n\mid d$，设 $d'=\frac{d}{n}$，$d=d'n$

$d\mid i$，则 $d'n\mid i$，即 $d'\mid \frac{i}{n}$ \[ \sum_{n\mid d}\mu(\frac{d}{n})\sum_{d\mid i}f(i)=\sum_{n\mid i}f(i)\sum_{d'\mid\frac{i}{n}}\mu(d') \] 当 $\frac{i}{n}$ 为 $1$，即 $i=n$ 时，$\sum_{d'\mid\frac{i}{n}}\mu(d')=1$，其余均为 $0$

所以

\[ \sum_{n\mid d}\mu(\frac{d}{n})F(d)=f(n) \]

反演结论

\[ d(ij)=\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,y)=1] \]