能力综合提升-数学-2

0x04 裴蜀定理

内容

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

证明

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

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

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

又 $0\leq 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\Longleftrightarrow\exists x,y,ax+by=1$

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

例题

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

0x05 乘法逆元

$ax\equiv 1\pmod b\Longrightarrow 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\neq 0$ 时，考虑 $\gcd(a,b) = \gcd(b, a\bmod b)$，先求解 $bx+(a\bmod b)y=\gcd(b, a\bmod b)$ 的解 $(x_0,y_0)$，带入可得

\[\begin{aligned} ax+by&=bx_0+(a\bmod b)y_0\\ &=bx_0+(a-\lfloor\frac{a}{b}\rfloor b)y_0\\ &=ay_0+b(x_0-\lfloor\frac{a}{b}\rfloor y_0) \end{aligned}\]

那么原方程的一个解就是 $(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\pmod b\Longleftrightarrow 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\pmod L$。

\[\begin{aligned}x+km&\equiv y+kn\pmod L\\k(m-n)&\equiv y-x\pmod L\\k(m-n)+pL&=y-x\end{aligned}\]

不妨记 $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$ 满足 $ax_0+by_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)=(kx_0+\frac{b}{d}kt,ky_0-\frac{a}{d}kt)$。

对于第二种情况，反证，假设存在这样的解使 $ax_0+by_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 求出解后，剩余系变成了 $\pmod{\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\pmod p$，$p\in \mathbb{P}$。如果 $p\nmid a$，那么也可以写成 $a^{p-1}\equiv 1\pmod p$。

注意：费马小定理的逆定理不成立，即不能从 $a^{p}\equiv a\pmod p$ 推出 $p\in \mathbb{P}$。满足 $a^{m}\equiv a\pmod 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$ 与任何小于它的正数互质。这保证了 $\bmod p$ 后不会出现 $0$。

互不相同：反证，$ax\equiv ay\pmod p\Longrightarrow a^{-1}ax\equiv a^{-1}ay\pmod p \Longrightarrow x\equiv y\pmod p$

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

\[\begin{aligned} a\times 2a\times 3a\times \cdots \times (p-1)a&\equiv 1\times 2\times 3\times\cdots\times (p-1) \pmod p \\ (p-1)!a^{p-1} &\equiv (p-1)! \pmod p\\ a^{p-1}&\equiv 1 \pmod p \end{aligned}\]

证毕。

法二：二项式定理

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

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

\[\begin{aligned} (b+1)^p&\equiv\dbinom{p}{p}b^p+\dbinom{p}{p-1}b^{p-1}+\cdots+\dbinom{p}{1}b^{1}+\dbinom{p}{0}b^{0}\pmod p\\ &\equiv \dbinom{p}{p}b^p + \dbinom{p}{0}b^{0}\pmod p\\ &\equiv b^p+1 \pmod p \end{aligned}\]

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

因此

\[\begin{aligned} a^p &\equiv (a-1)^p+1 \pmod p\\ &\equiv (a-2)^p+2 \pmod p\\ &\cdots\\ &\equiv (a-a)^p+a \pmod p\\ &\equiv a \pmod p\\ \end{aligned}\]

证毕。

法三：拉格朗日定理

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

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

\[a^{p-1}\equiv a^{mk}\equiv (a^k)^m\equiv 1^m\equiv 1\pmod p\]

证毕。

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

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

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

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

递推线性求逆元

起始条件 $1^{-1}\equiv 1\pmod p$。

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

\[\begin{aligned} kq+r&\equiv 0\pmod p\\ (kq+r)(q^{-1})(r^{-1})&\equiv 0\pmod p\\ kr^{-1}+q^{-1}&\equiv 0\pmod p\\ q^{-1}&\equiv-kr^{-1}\pmod p\\ q^{-1}&\equiv-\lfloor\frac{p}{q}\rfloor (p\bmod q)^{-1}\pmod p\\ \end{aligned}\]

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

另外，写代码的时候，我们不希望它计算后是个负数，因此一般写成 $q^{-1}=(p-\lfloor\frac{p}{q}\rfloor)(p\bmod q)^{-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^{\varphi(m)}\equiv 1\pmod m$。

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

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

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

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

扩展欧拉定理

\[a^b\equiv\begin{cases} a^{b\bmod \varphi(m)},&\gcd(a,m)=1\\a^b, &\gcd(a,m)\neq 1, b< \varphi(m)\\a^{(b \bmod \varphi(m))+\varphi(m)},&\gcd(a, m)\neq 1, b\geq \varphi(m) \end{cases}\pmod m\]

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

例题

求 $2\uparrow\uparrow\infty\bmod p$。

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

\[2\uparrow\uparrow\infty\equiv 2^{2\uparrow\uparrow\infty\bmod\varphi(p)+\varphi(p)}\pmod p\]

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

1. $n>1\Longrightarrow 2\mid \varphi(n)$

2. $\varphi(2n)\leq n$

可知，最坏情况下每两次迭代 $\varphi(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{cases} x\equiv a_1&\pmod {b_1}\\ x\equiv a_2&\pmod {b_2}\\ \vdots\\ x\equiv a_n&\pmod {b_n} \end{cases}\]

这里 $b_i$ 两两互质。

推导过程

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

\[\begin{cases} x_1\equiv a_1&\pmod {b_1}\\ x_1\equiv 0&\pmod {b_2}\\ \vdots\\ x_1\equiv 0&\pmod {b_n} \end{cases} \begin{cases} x_2\equiv 0&\pmod {b_1}\\ x_2\equiv a_2&\pmod {b_2}\\ \vdots\\ x_2\equiv 0&\pmod {b_n} \end{cases} \cdots \begin{cases} x_n\equiv 0&\pmod {b_1}\\ x_n\equiv 0&\pmod {b_2}\\ \vdots\\ x_n\equiv a_n&\pmod {b_n} \end{cases}\]

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

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

\[\begin{cases} x_1\equiv a_1&\pmod {b_1}\\ x_1\equiv 0&\pmod {b_2}\\ \vdots\\ x_1\equiv 0&\pmod {b_n} \end{cases} \Longrightarrow \begin{cases} y_1\equiv 1&\pmod {b_1}\\ y_1\equiv 0&\pmod {b_2}\\ \vdots\\ y_1\equiv 0&\pmod {b_n} \end{cases}\]

求出了 $y_1$ 立刻就有 $x_1=a_1\times y_1$。继续化简，有 \(\begin{cases} y_1\equiv 1&\pmod {b_1}\\ y_1\equiv 0&\pmod {\prod\limits_{i=2}^n b_i} \end{cases}\)

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

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

结论

1. 计算所有模数的积 $b=\prod\limits_{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\limits_{i=1}^n a_i\times c_i \pmod 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{cases} x\equiv a_1&\pmod{b_1}\\ x\equiv a_2&\pmod{b_2} \end{cases}\]

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

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

\[\begin{cases} x_h\equiv 0&\pmod{b_1}\\ x_h\equiv 0&\pmod{b_2} \end{cases}\]

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

\[x\equiv x_0\pmod{\operatorname{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\pmod m\]

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

推导过程

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

令 $x=qB+r$，就有

\[\begin{aligned}a^{qB+r}&\equiv b\\a^{qB}&\equiv b\times a^{-r}\pmod m \end{aligned}\]

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