分数取模学习笔记

· · 个人记录

exgcd

前言

在取模的时候，加法、减法、乘法都是满足分配律的，也就是说先加/减/乘再取模和先取模再加/减/乘是一样的。但是只有除法例外，所以为了做除法的取模，我们需要请出伟大的逆元，而为了求出逆元，我们需要一些新的工具....

Part 1:裴蜀定理

设两个正整数 a, b 那么任何他们最大公因数的倍数都可以被一组 (x,y) 表示出来，形式化地说

\exists x,y \in \mathbb{Z},ax+by=k \times gcd(a,b),\forall a,b \in \mathbb{N}^+,k \in \mathbb{Z}

这个不难证明，不妨设 gcd(a,b)=G,a=pG,b=qG ，则 ax+by=pGx+qGy=(px+qy)G=(px+qy) \times gcd(a,b) ，得证

Part 2:Exgcd（拓展欧几里得算法）

普通的欧几里得算法是用来求 gcd(a,b) 的，而拓展欧几里得算法在此基础上还顺便解决了一个问题，它找到了使 ax+by=gcd(a,b) 成立的一组整数解 (x,y).

注意：开始跃迁了

假设我们能够找到一组 (x_1,y_1) ，满足 bx_1+(a\bmod b)x_2=G ，那么与 ax+by=G 联立可得

ax+by=bx_1+(a-b\times(a/b))y_1

化简得

ax+by=ay_1+b(x_1-\frac{a}{b}\times y_1)

tips：这里的 G 还是 gcd(a,b)

所以必有一组解是 x=y_1,y=x_1-\frac{a}{b}\times y_1 。但是有个问题： x_1,y_1 怎么求呢？

我们观察两个式子

ax+by=gcd(a,b) bx_1+(a\bmod b)y_1=gcd(a,b)

惊讶地发现等式右边相同，而又因为 x,y 由 x_1,y_1 决定，所以如果把他们看成变量，那么整个式子其实就只有前面系数的变化，我们可以用一个递归函数来解决问题

void exgcd(int a, int b){
    exgcd(b,a%b);
}

长得是不是很像求最大公因数的程序？下面我们要给它补全。首先，为了避免死循环，我们要为它寻找一个终止条件。根据平常求gcd的经验，当 b=0 时终止，此时 a=G ，当 x=1,y=0 时 ax+by=G，满足条件。（其实 y 取什么值都没问题的，但是为了方便我们一般用 0）。最后别忘了把 x,y 用我们之前推出来的公式一层层往上迭代。

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

至此，我们成功找到了 ax+by=gcd(a,b) 的一组解 (x,y) ，可是这又有什么用呢？

Part 3:乘法逆元

定义：我们定义当 ax \equiv1(\bmod b) 时， x 被称为 a 在模 b 意义下的乘法逆元（即模 b 情况下的倒数）

我们都知道，除以一个数等于乘上它的倒数，所以如果我们要在模 p 意义下除以一个数，只需要乘上它在模 p 意义下的乘法逆元即可。乘法逆元是我们解决分数取模的有力工具

那么，怎么求乘法逆元呢？我们回到它的定义式

ax\equiv 1

由于是在模 b 意义下，所以左边可以加任意个 b 而使得同余符号仍成立，于是我们不妨令 ax+by=1

是不是很眼熟？我们刚刚解决过的 ax+by=gcd(a,b) 的问题又出现了，但是在这里，它强制要求 a,b 互质。用拓展欧几里得算法我们可以轻松地求出一组满足条件的解 (x,y) （事实上， a,b 互质是存在一个 x 满足这个定义式的充要条件）。但是很多时候求出来的 x 未必是最小的非负整数，这个时候我们可以通过对 x 批量加减 b 来找到其它所有解，因为：

形如 x+kb 的 x' 必然满足定义式：

ax'=a(x+kb)=ax+akb\equiv ax\equiv 1(\bmod b), k\in \mathbb{Z}

满足定义式的 x' 必然形如 x+kb：

设 x'=x+\Delta x

\because ax'=ax+a\Delta x\equiv1+a\Delta x\equiv 1(\bmod b) \therefore a\Delta x\equiv0(\bmod b) \because gcd(a,b)=1 \therefore \Delta x=kb,k\in \mathbb{Z}

可得 x'=x+kb ，得证

所以通过对 x 加减若干个 b 的方式，我们可以找到一个最小的正整数解 x_0 它就是我们要找的乘法逆元

x=(x%b+b)%b;//证了一大堆，代码很简洁

Part 4:分数取模

但是我们平时看到的分数取模是形如 x\equiv\frac{a}{b}(\bmod p) 的呀，怎么用上逆元呢？

这个时候可以应该按以下步骤做：

step1: 把 a,b 通通对 p 取模

step2: 求出 b 在模 p 情况下的逆元 b^{-1}

step3: 求解 x=a\times b^{-1} ，别忘了随时对 p 取模

Part 5:代码

这里有份优美的代码，可惜位置太小，写不下