能力综合提升-数学-2

0x04 裴蜀定理

内容

$a,b$ 不全为 $0$ 时，$\mathrm{\forall }x,y,gcd(a,b)\mid ax+by$，且 $\mathrm{\exists }x,y,ax+by=gcd(a,b)$。

证明

对于第一点，$gcd(a,b)\mid a\wedge gcd(a,b)\mid b⟹gcd(a,b)\mid ax\wedge gcd(a,b)\mid by⟹gcd(a,b)\mid ax+by$。

对于第二点，记 $d=gcd(a,b),s=\underset{ax+by>0}{min}(ax+by)$。

设 $a=ps+r$，则 $r=a-ps=a-p(ax+by)=a(1-px)+b(-py)$。

又 $0\le r<s$ 且 $s$ 是最小的满足 $s=ax+by$ 的正数，可知 $r=0$。

那么就是 $s\mid a$，同理有 $s\mid b$，故 $s\mid gcd(a,b)$。

又由第一点 $gcd(a,b)\mid ax+by$ 知 $gcd(a,b)\mid s$。

那么 $s=gcd(a,b)$。

推论

$gcd(a,b)=1⟺\mathrm{\exists }x,y,ax+by=1$

$(a,b)$ 这种二维的情况可以扩展到 $n$ 维 $(a_1,a_2,\cdots ,a_n)$。

例题

给定互质的正整数 $a,b$，记 $S=d\mid d=ax+by,x\ge 0,y\ge 0$，求 $max(N\setminus S)$。保证一定有解。

0x05 乘法逆元

$ax\equiv 1(\mathrm{mod}b)⟹x$ 是 $a$ 在模 $b$ 意义下的逆元，记作 $a^{-1}$。

扩展欧几里得算法

void exgcd(int a, int b, int &x, int &y)
{
    if(b == 0) x = 1, y = 0;
    else exgcd(b, a % b, y, x), y -= a / b * x;
}

用来求解形如 $ax+by=gcd(a,b)$ 的方程的一组解。

$b=0$ 时，$gcd(a,b)=a$，那么显然有 $x=1$，$y$ 可以是任意数，这里令 $y=0$ （其实别的也无所谓）。

$b\ne 0$ 时，考虑 $gcd(a,b)=gcd(b,amodb)$，先求解 $bx+(amodb)y=gcd(b,amodb)$ 的解 $(x_0,y_0)$，带入可得

$$\begin{array}{rl}ax+by& =b{x}_0+(amodb)y_0\\ & =b{x}_0+(a-\lfloor \frac{a}{b}\rfloor b)y_0\\ & =a{y}_0+b(x_0-\lfloor \frac{a}{b}\rfloor y_0)\end{array}$$

那么原方程的一个解就是 $(y_0,x_0-\lfloor \frac{a}{b}\rfloor y_0)$。

要求出所有解，我们显然可以注意到，对 $x$ 加上（或减去）若干个 $b$ 后依然能保证满足方程。若方程的解是 $(x,y)$，那么通解就是 $(x+kb,y-ka),k\in \mathbb{Z}$（反证可证没有漏掉其他的解）。

如果我们想求最小的正数 $x$，可以这么写：x = (x % b + b) % b，它可以处理负数。

回到求逆元问题上来，$ax\equiv 1(\mathrm{mod}b)⟺ax+by=1$，因此只要 $a,b$ 互质 就能使用扩展欧几里得算法求解。和欧几里得算法一样，时间复杂度 $O(\log p)$。

int inv(int a, int b)
{
    int x, y; exgcd(a, b, x, y);
    return (x % b + b) % b;
}

例题

求解 $x+km\equiv y+kn(\mathrm{mod}L)$。

$$\begin{array}{rl}x+km& \equiv y+kn(\mathrm{mod}L)\\ k(m-n)& \equiv y-x(\mathrm{mod}L)\\ k(m-n)+pL& =y-x\end{array}$$

不妨记 $u=y-x,v=m-n$，也就是要解不定方程 $kv+pL=u$。

考虑 exgcd 的原理，是用来求解形如 $ax+by=gcd(a,b)$ 的方程的一组解，则

引理：对于不定方程 $ax+by=c$，记 $d=gcd(a,b)$。

1. 若 $d\mid c$ 则方程有整数解，且可以通过 exgcd 求出；

2. 若 $d\nmid c$ 则方程无解。

证明：

对于第一种情况，考虑 $ax+by=d$ 的方程，由裴蜀定理可知必存在 $x_0,y_0$ 满足 $a{x}_0+b{y}_0=d$。因此方程的通解是 $(x,y)=(x_0+\frac{b}{d}t,y_0-\frac{a}{d}t),t\in \mathbb{Z}$。 记 $c=kd$，则两边同乘 $k$ 有 $a(kx)+b(ky)=c$，也就找到了特解 $(kx,ky)=(k{x}_0+\frac{b}{d}kt,k{y}_0-\frac{a}{d}kt)$。

对于第二种情况，反证，假设存在这样的解使 $a{x}_0+b{y}_0=c$。由于 $d=gcd(a,b)$，可化为 $d(\frac{a}{d}{x}_0+\frac{b}{d}{y}_0)=c$，即 $d\mid c$，矛盾。

于是，当 $gcd(k,p)\nmid u$ 时，方程无解。否则，先用 exgcd 解出 $kv+pL=gcd(k,p)$ 的解，再乘上倍数即可。

不过需要注意：

1. $y-x,m-n<0$ 的情况，最好使用 x = (x % L + L) % L 这样的语句来保证取值非负。

2. exgcd 求出解后，剩余系变成了 $(\mathrm{mod}\frac{L}{d})$，对于后面的非负操作要对 $L$ 修改。

3. #define int ll。

signed main()
{
    ll x, y, m, n, L;
    read(x, y, m, n, L);
    ll u = ((x - y) % L + L) % L;
    ll v = ((n - m) % L + L) % L;
    ll d = gcd(v, L);
    if(u % d != 0)
        puts("Impossible"), exit(0);
    ll a, b;
    exgcd(v, L, a, b);
    L /= d;
    a = (a % L + L) % L;
    ll ans = a * (u / d) % L;
    write('\n', ans);
    return 0;
}

费马小定理

$a^p\equiv a(\mathrm{mod}p)$，$p\in \mathbb{P}$。如果 $p\nmid a$，那么也可以写成 $a^{p-1}\equiv 1(\mathrm{mod}p)$。

注意：费马小定理的逆定理不成立，即不能从 $a^p\equiv a(\mathrm{mod}p)$ 推出 $p\in \mathbb{P}$。满足 $a^m\equiv a(\mathrm{mod}m)$ 的合数 $m$ 被称为 Carmichael 数（参见 Miller-Rabin 内容）。

由于证明方法非常美妙，我打算写三种。

法一：简化剩余系

仅证 $p\nmid a$ 即 $gcd(a,p)=1$ 的情况。

考虑 $S=1,2,3,\cdots ,p-1$，$aS=a,2a,3a,\cdots ,(p-1)a$，构造出的 $aS$ 的性质：每个元素仍与 $p$ 互质且在模 $p$ 意义下互不相同。

互质：$gcd(a,p)=1$ 且质数 $p$ 与任何小于它的正数互质。这保证了 $modp$ 后不会出现 $0$。

互不相同：反证，$ax\equiv ay(\mathrm{mod}p)⟹a^{-1}ax\equiv a^{-1}ay(\mathrm{mod}p)⟹x\equiv y(\mathrm{mod}p)$

这两个性质保证了 $aS$ 是 $S$ 在 $modp$ 的一个排列。

$$\begin{array}{rl}a\times 2a\times 3a\times \cdots \times (p-1)a& \equiv 1\times 2\times 3\times \cdots \times (p-1)(\mathrm{mod}p)\\ (p-1)!a^{p-1}& \equiv (p-1)!(\mathrm{mod}p)\\ a^{p-1}& \equiv 1(\mathrm{mod}p)\end{array}$$

证毕。

法二：二项式定理

考虑二项式系数 ${\displaystyle (\genfrac{}{}{0ex}{}{p}{n})}=\frac{p!}{n!(p-n)!}$。限定 $0<n<p$ 则分子上的 $p$ 不会被约去，就有 $p\mid {\displaystyle (\genfrac{}{}{0ex}{}{p}{n})}$。

再考虑 $(b+1{)}^p$ 的二项式展开，有

$$\begin{array}{rl}(b+1{)}^p& \equiv {\displaystyle (\genfrac{}{}{0ex}{}{p}{p})}{b}^p+{\displaystyle (\genfrac{}{}{0ex}{}{p}{p-1})}{b}^{p-1}+\cdots +{\displaystyle (\genfrac{}{}{0ex}{}{p}{1})}{b}^1+{\displaystyle (\genfrac{}{}{0ex}{}{p}{0})}{b}^0(\mathrm{mod}p)\\ & \equiv {\displaystyle (\genfrac{}{}{0ex}{}{p}{p})}{b}^p+{\displaystyle (\genfrac{}{}{0ex}{}{p}{0})}{b}^0(\mathrm{mod}p)\\ & \equiv b^p+1(\mathrm{mod}p)\end{array}$$

（注：这个结论也可以由数学归纳法证明）

因此

$$\begin{array}{rl}{a}^p& \equiv (a-1{)}^p+1(\mathrm{mod}p)\\ & \equiv (a-2{)}^p+2(\mathrm{mod}p)\\ & \cdots \\ & \equiv (a-a{)}^p+a(\mathrm{mod}p)\\ & \equiv a(\mathrm{mod}p)\end{array}$$

证毕。

法三：拉格朗日定理

当 $p$ 为质数时，所有与 $p$ 互质的整数模 $p$ 的非零余数构成一个乘法群，记作 $(\mathbb{Z}/p\mathbb{Z}{)}^{\ast }$，它的阶是 $p-1$。

考虑由 $a$ 生成的循环子群，它的阶就是 $a$ 的阶，即满足 $a^k\equiv 1(\mathrm{mod}p)$ 的最小正数 $k$。由拉格朗日定理，有限群中任意子群的阶必整除原群的阶，也就是 $k\mid p-1⟹p-1=km,m\in \mathbb{Z}$。于是

$$a^{p-1}\equiv a^{mk}\equiv (a^k{)}^m\equiv 1^m\equiv 1(\mathrm{mod}p)$$

证毕。

另外，费马小定理实质上是欧拉定理的一种特殊情况，下文会谈。

回到求逆元问题上来，由于 $a^{p-1}\equiv 1(\mathrm{mod}p)$，可以发现 $a\times a^{p-2}\equiv 1(\mathrm{mod}p)$，于是 $x=a^{p-2}$ 就是所求的解。快速幂即可求出，时间复杂度 $O(\log p)$。

int inv(int a, int p)
{
    return fastpow(a, p - 2, p);
}

可以发现能用费马小定理的情况一定能用扩展欧几里得算法得出（$p\in \mathbb{P}⟹gcd(a,p)=1$），反之则不行。

递推线性求逆元

起始条件 $1^{-1}\equiv 1(\mathrm{mod}p)$。

记 $p=kq+r$，那么有

$$\begin{array}{rl}kq+r& \equiv 0(\mathrm{mod}p)\\ (kq+r)(q^{-1})(r^{-1})& \equiv 0(\mathrm{mod}p)\\ k{r}^{-1}+q^{-1}& \equiv 0(\mathrm{mod}p)\\ q^{-1}& \equiv -k{r}^{-1}(\mathrm{mod}p)\\ q^{-1}& \equiv -\lfloor \frac{p}{q}\rfloor (pmodq{)}^{-1}(\mathrm{mod}p)\end{array}$$

其中 $(pmodq)<p$，其逆元的值已经被计算出来了。

另外，写代码的时候，我们不希望它计算后是个负数，因此一般写成 $q^{-1}=(p-\lfloor \frac{p}{q}\rfloor )(pmodq{)}^{-1}$。

int inv[Max];
void Pre(int Max, int p)
{
    inv[1] = 1;
    F(i, 2, p - 1)
        inv[i] = (p - p / i) * inv[p % i] % p;
}

0x06 欧拉定理 & 扩展欧拉定理

欧拉定理

若 $gcd(a,m)=1$，则 $a^{\phi (m)}\equiv 1(\mathrm{mod}m)$。

证明非常类似费马小定理的证明。

把费马小定理证明的法一中的 $S$ 改为与 $m$ 互质的集合，其他过程同理。

把费马小定理证明的法三中的 $(\mathbb{Z}/p\mathbb{Z}{)}^{\ast }$ 改为 $(\mathbb{Z}/m\mathbb{Z}{)}^{\ast }$，它的阶是 $\phi (m)$，其他过程同理。

当 $m\in \mathbb{P}$ 时，由于 $\phi (m)=m-1$，立刻退化成费马小定理。

扩展欧拉定理

$$a^b\equiv \{\begin{array}{ll}{a}^{bmod\phi (m)},& gcd(a,m)=1\\ a^b,& gcd(a,m)\ne 1,b<\phi (m)\\ a^{(bmod\phi (m))+\phi (m)},& gcd(a,m)\ne 1,b\ge \phi (m)\end{array}(\mathrm{mod}m)$$

第一种情况可以由欧拉定理直接得到，第二种情况的意思是无需使用扩展欧拉定理计算，时间复杂度可以接受，第三种情况证明太长不看。

例题

求 $2\uparrow \uparrow \mathrm{\infty }modp$。

对于指数很大的数要首先想到扩展欧拉定理。由于 $p$ 是任意给定的，不能保证 $gcd(2,p)=1$，因此采用第三行式子（对于第一种情况依然可行）。于是

$$2\uparrow \uparrow \mathrm{\infty }\equiv 2^{2\uparrow \uparrow \mathrm{\infty }mod\phi (p)+\phi (p)}(\mathrm{mod}p)$$

注意看，此时对 $2\uparrow \uparrow \mathrm{\infty }$ 的模数由 $p$ 变为了 $\phi (p)$，不难想到模数最终会递归到 $1$，此时返回 $0$ 即可。下面计算此过程的复杂度。由 $\phi (n)$ 的性质，

1. $n>1⟹2\mid \phi (n)$

2. $\phi (2n)\le n$

可知，最坏情况下每两次迭代 $\phi (p)$ 先变成偶数再减半，这个时间复杂度是 $O(\log p)$ 的，可以通过。

int f(int p)
{
    if(p == 1) return 0;
    int Phi = phi(p);
    return fastpow(2, f(Phi) + Phi, p);
}

0x07 中国剩余定理 & 扩展中国剩余定理

中国剩余定理

中国剩余定理是用来求解如下形式的一元线性同余方程组：

$$\{\begin{array}{ll}x\equiv a_1& (\mathrm{mod}{b}_1)\\ x\equiv a_2& (\mathrm{mod}{b}_2)\\ ⋮\\ x\equiv a_n& (\mathrm{mod}{b}_n)\end{array}$$

这里 $b_i$ 两两互质。

推导过程

考虑把方程组分解，若能分别解出下列 $n$ 个方程的解，

$$\{\begin{array}{ll}{x}_1\equiv a_1& (\mathrm{mod}{b}_1)\\ x_1\equiv 0& (\mathrm{mod}{b}_2)\\ ⋮\\ x_1\equiv 0& (\mathrm{mod}{b}_n)\end{array}\{\begin{array}{ll}{x}_2\equiv 0& (\mathrm{mod}{b}_1)\\ x_2\equiv a_2& (\mathrm{mod}{b}_2)\\ ⋮\\ x_2\equiv 0& (\mathrm{mod}{b}_n)\end{array}\cdots \{\begin{array}{ll}{x}_n\equiv 0& (\mathrm{mod}{b}_1)\\ x_n\equiv 0& (\mathrm{mod}{b}_2)\\ ⋮\\ x_n\equiv a_n& (\mathrm{mod}{b}_n)\end{array}$$

就能得到 $x=\sum _{i=1}^n{x}_i$。

以第一个方程为例，可以进一步转换：

$$\{\begin{array}{ll}{x}_1\equiv a_1& (\mathrm{mod}{b}_1)\\ x_1\equiv 0& (\mathrm{mod}{b}_2)\\ ⋮\\ x_1\equiv 0& (\mathrm{mod}{b}_n)\end{array}⟹\{\begin{array}{ll}{y}_1\equiv 1& (\mathrm{mod}{b}_1)\\ y_1\equiv 0& (\mathrm{mod}{b}_2)\\ ⋮\\ y_1\equiv 0& (\mathrm{mod}{b}_n)\end{array}$$

求出了 $y_1$ 立刻就有 $x_1=a_1\times y_1$。继续化简，有 $\{\begin{array}{ll}{y}_1\equiv 1& (\mathrm{mod}{b}_1)\\ y_1\equiv 0& (\mathrm{mod}\prod _{i=2}^n{b}_i)\end{array}$

记 $p_i=\prod _{j\ne i}{b}_j$，于是 $y_1=1+k{b}_1=m{p}_1$，问题也就转化为了解 $m{p}_1-k{b}_1=1$ 这个不定方程。注意到前提条件保证 $b_i$ 两两互质，因此 $gcd(p_1,b_1)=1$，可以使用 exgcd 求解。

于是便可以按这种方法，求出上面的 $n$ 个方程组的解，然后便得到了原方程的整数解。

结论

1. 计算所有模数的积 $b=\prod _{i=1}^n{b}_i$

2. 对于第 $i$ 个方程，

   1. 计算 $p_i=\frac{b}{b_i}$

   2. exgcd 计算 $p_i$ 在模 $b_i$ 意义下的逆元 $p_i^{-1}$

   3. 计算 $c_i=p_i\times p_i^{-1}$（不要对 $b_i$ 取模）

3. 唯一解为 $x=\sum _{i=1}^n{a}_i\times c_i(\mathrm{mod}b)$

#define int __int128
signed main()
{
    read(n);
    F(i, 1, n)
        read(b[i], a[i]), B *= b[i];
    int ans = 0;
    F(i, 1, n)
    {
        int p = B / b[i];
        ans += a[i] * p * inv(p, b[i]);
        // 因为用了 __int128 很充裕，如果是 long long 要龟速乘且每步取模
    }
    write('\n', ans % B);
    return 0;
}

扩展中国剩余定理

中国剩余定理无法处理模数不互质的情况，这是中国剩余定理的原理所决定的。它的解中 “$p_i$ 在模 $b_i$ 意义下的逆元 $p_i^{-1}$” 在 $p_i,b_i$ 不互质的情况下，根本不存在。因此我们需要完全放弃中国剩余定理的思路，转到合并方程的方向上来。

推导过程

仅考虑两个方程的方程组，

$$\{\begin{array}{ll}x\equiv a_1& (\mathrm{mod}{b}_1)\\ x\equiv a_2& (\mathrm{mod}{b}_2)\end{array}$$

它等价于 $x=k_1{b}_1+a_1=k_2{b}_2+a_2$，移项得 $k_1{b}_1-k_2{b}_2=a_2-a_1$。这显然是一个不定方程，利用裴蜀定理确定是否有解：如果 $gcd(b_1,b_2)\nmid a_2-a_1$ 则无解。

利用 exgcd 可以求出不定方程的解（前面例题有讲），于是构造出了一个这样的 $x_0$。但是通解是什么呢？根据线性代数的知识，通解等于特解加齐次解，它对应的齐次方程就是

$$\{\begin{array}{ll}{x}_h\equiv 0& (\mathrm{mod}{b}_1)\\ x_h\equiv 0& (\mathrm{mod}{b}_2)\end{array}$$

显然它的解是 $x_h=k\mathrm{lcm}(b_1,b_2)$，于是得到了 $x=x_0+k\mathrm{lcm}(b_1,b_2)$，也就是

$$x\equiv x_0(\mathrm{mod}\mathrm{lcm}(b_1,b_2))$$

这就是两个同余方程合并为一个的结果。

因此，反复的将两个方程合并为一个，最终剩余的结果就是解系。

#define int __int128
typedef pair<int, int> pii;
#define mp(a, b) make_pair(a, b)
pii a[maxn];
pii merge(pii x, pii y)
{
    int a1 = x.first, b1 = x.second;
    int a2 = y.first, b2 = y.second;
    int u = a2 - a1, d = gcd(b1, b2);
    if(u % d != 0)
        assert(1);
    int l = b1 * b2 / d;
    int p, q;
    exgcd(b1, b2, p, q);
    p = (p % b2 + b2) % b2;
    p *= u / d;
    int ans = a1 + p * b1;
    ans = (ans % l + l) % l;
    return mp(ans, l);
}
signed main()
{
    read(n);
    F(i, 1, n)
        read(a[i].second, a[i].first);
    F(i, 2, n)
        a[i] = merge(a[i - 1], a[i]);
    write('\n', a[n].first);
    return 0;
}

0x08 BSGS & 扩展 BSGS

BSGS

BSGS（Baby-Step Giant-Step，大步小步算法）常用于求解离散对数问题。具体的，它能在 $O(\sqrt{m})$ 的时间复杂度内求解

$$a^x\equiv b(\mathrm{mod}m)$$

其中 $gcd(a,m)=1$。

推导过程

正如“大步小步”的名字一样，主要在于先小步小步的处理，然后大步大步的处理，跟分块相似。

令 $x=qB+r$，就有

$$\begin{array}{rl}{a}^{qB+r}& \equiv b\\ a^{qB}& \equiv b\times a^{-r}(\mathrm{mod}m)\end{array}$$

预处理每个 $b\times a^{-r}$ 到哈希表，枚举每个 $q$ 即可。考虑时间复杂度，显然让 $B=\sqrt{m}$ 时两边的处理次数平均最少，为 $O(\sqrt{m})$。