【数论】Exgcd/乘法逆元

## 说明 本题单主要包括 Exgcd 和乘法逆元的应用，掺杂了一些费马小定理/欧拉定理的内容。 以下算法与数论说明全文选自 [**数学：Exgcd 与乘法逆元的漫步**](https://www.luogu.com.cn/blog/LinearExpectation/exgcd-inv)，您可以在博客链接中阅读。 以下是练习题目： - [P3811 【模板】乘法逆元](https://www.luogu.com.cn/problem/P3811) - [P5431 【模板】乘法逆元2](https://www.luogu.com.cn/problem/P5431) - [P2613 【模板】有理数取余](https://www.luogu.com.cn/problem/P2613) - [P1082 [NOIP2012 提高组] 同余方程](https://www.luogu.com.cn/problem/P1082) - [P6217 简单数论题](https://www.luogu.com.cn/problem/P6217) - [P1762 偶数](https://www.luogu.com.cn/problem/P1762) - [P6299 差别](https://www.luogu.com.cn/problem/P6299) - [P2054 [AHOI2005]洗牌](https://www.luogu.com.cn/problem/P2054) - [P1641 [SCOI2010]生成字符串](https://www.luogu.com.cn/problem/P1641) ## $\bold{Part\ 1\ 参考资料}$ - **[OI-Wiki：$\gcd$ 以及 $\rm Exgcd$ 相关](https://oi-wiki.org/math/gcd/#_7)** - **[OI-Wiki：乘法逆元相关](https://oi-wiki.org/math/inverse/)** 掌握这篇学习笔记，你需要的知识是模意义下的运算以及基本的代数变换。 其他的数学基础与拓展是：  ## $\bold{Part\ 2\ Exgcd}$ 我们集中注意力在一个问题上：$ax+by=\gcd(a,b)$，这个不定方程如何解决？ 首先存在 $ax_1+by_1=\gcd(a,b)$，其次当我们将方程用 $(a\bmod b)$ 和 $a$ 来代入的时候可以发现，同时还存在 $bx_2+(a\bmod b)y_2=\gcd(b,a\bmod b)$。这时候我们找出了两个符合题目条件的式子。 在我们学习最大公约数时，欧几里得定理提出 $\gcd(a,b)=\gcd(b,a\bmod b)$，所以我们已经列出的两个式子右半边相等，于此相对地，左半边也相等，从而我们可以将这两个式子联立形成一个等式： $$ax_1+by_1=bx_2+(a\bmod b)y_2$$ 我们还知道，对于一个取模式存在 $a\bmod b=a-\bigg(\left\lfloor\dfrac{a}{b}\right\rfloor\times b\bigg)$。 于是我们代入原式并化简： $$ax_1+by_1=bx_2+\bigg(a-\left\lfloor\dfrac{a}{b}\right\rfloor\times b\bigg)y_2$$ 乘法分配律拆开括号： $$ax_1+by_1=bx_2+ay_2-\left\lfloor\dfrac{a}{b}\right\rfloor\times by_2$$ 提取公因式进行因式分解： $$ax_1+by_1=ay_2+b(x_2-\left\lfloor\dfrac{a}{b}\right\rfloor y_2)$$ 我们可以将两边简单地对等起来，得到一个具有普遍规律的式子： $$x_1=y_2\quad y_1=x_2-\left\lfloor\dfrac{a}{b}\right\rfloor y_2$$ 这个式子的意义是，我们可以缩减 $x$ 和 $y$ 的范围，递归求解了。 ```cpp 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),t=x; x=y; y=t-(a/b)*y; return d; } ``` ## $\bold{Part\ 3\ 逆元基础}$ ### 什么是逆元？ 假设存在一个自洽的代数系统 $S$，存在一种运算 $\circ$。对于其中的某一元素 $a$，如果存在 $a\circ e=a$，那么我们称 $e$ 是该系统中对于 $\circ$ 运算的单位元。 而如果存在一个元素 $a$ 与另一元素 $x$，使得 $a\circ x=e$，那么 $x$ 称为 $a$ 在该系统中对于该运算的右逆元，记为 $a^{-1}_{r}$。反之，如果存在 $x$ 满足 $x\circ a=e$，那么 $x$ 称为 $a$ 在该系统中对于该运算的左逆元，记为 $a^{-1}_{l}$。 而据我们所知，在整数系统中，存在相当多一部分的运算是左右对称的，即 $a\circ x=x\circ a$，那么我们简单地称 $x$ 为 $a$ 的逆元，记为 $a^{-1}$。对于我们目前研究的整数系统，存在最为常见的对称运算是加法与乘法。 加法的单位元是 $0$，即 $a+0=a\ (a\in Z)$，而乘法的单位元则是 $1$，即 $1\times a=a\ (a\in Z)$。对于这两种运算，不难想到加法逆元即为原数相反数，而乘法逆元则为原数的倒数。 ### 模意义下的乘法逆元 在模 $p$ 意义下，如果 $ax=1$，那么 $x$ 是 $a$ 的乘法逆元，记为 $a^{-1}$。更加严谨地，存在： $$ax\equiv 1\pmod p$$ 为了使得题目更加容易求解，我们可以令 $p$ 是质数，我们先来讨论这种情况。 ## $\bold{Part\ 4\ 较高复杂度求解}$ ### 费马小定理与快速幂 **[$\bold{LinearExpectation}$：费马小定理与欧拉定理的证明及应用](https://www.luogu.com.cn/blog/LinearExpectation/Euler-Theorem-Fermat-Little-Theorem)** 对于素数 $p$，当 $\gcd(a,p)=1$ 时，存在： $$a^{p-1}\equiv 1\pmod p$$ 将原式替换进去，就可以得到： $$a^{p-1}\equiv ax\pmod p$$ 两边同时除以 $a$，可以得到： $$x\equiv a^{p-2}\pmod p$$ 显然，我们只需要求出 $a^{p-2}\bmod p$ 即可。但是这样的一个式子，如果使用循环累乘，达到单个数 $O(p)$ 的复杂度，就过于难看了，无法通过模板题。于是我们使用[快速幂](https://www.luogu.com.cn/blog/cicos/quickpow)，以分治的思想进行解决，可以实现单个数 $O(\log p)$。 这样的方法，整体复杂度为 $O(n\log p)$，不是很容易被接受。 对于欧拉定理，我们可以得到更为一般的结论，即： $$x\equiv a^{\varphi(p)-1}\pmod p$$ 其中[欧拉函数](https://www.luogu.com.cn/blog/LinearExpectation/Scientifically-calculate-Euler-function)可以用链接博客中的方法线性预处理，得到结果后调用即可。 ### 扩展欧几里得 Exgcd 对于题目中给出的式子： $$ax\equiv 1\pmod p$$ 很容易转化为一个不定方程： $$ax+by=1$$ 那么使用上文说明完毕的扩展欧几里得 Exgcd 很容易解决这个问题。事实上，我们只要在原方程两边同时除以 $\gcd(a,b)$ 即可得到上述的式子。 但是对于每个数，我们的时间复杂度仍是 $\log$ 级别的，虽然后面跟的不再是 $p$ 了，但是这个复杂度，在我们看来仍然偏高了。 ## $\bold{Part\ 5\ 线性求解}$ ### 线性求逆元 考虑在 $O(n)$ 的线性时间复杂度中完成在模 $p$ 意义下对于 $1\sim n$ 逆元的求取。 显然，对于边界条件 $a=1$，存在 $a^{-1}\equiv 1\pmod p$，其原因是 $1\times 1\equiv 1\pmod p$ 显然恒成立。接着我们考虑进行一般化，对于递归情况 $i^{-1}$，我们要尝试着拆分 $p$ 使其能被更基本的元素进行表示。 与 $i$ 相关地，我们将其对 $i$ 进行整除，分成商与余数两个部分，即 $k=\left\lfloor{\dfrac{p}{i}}\right\rfloor$，$j(p\bmod i)$。这时候我们容易用 $k.j$ 表示出 $p$，也就是 $p=ki+j$，对于模 $p$ 意义下的情况，表示为 $ki+j\equiv 0\pmod p$。 我们容易在 $i,j$ 同时存在时将其转化为逆元的表示方法，具体操作是在两边同时乘上 $i^{-1}\times j^{-1}$，对于底数相同的部分抵消后就得到 $kj^{-1}+i^{-1}\equiv 0\pmod p$。然后我们移项，利用主元法将 $i^{-1}$ ；留在左边，并且代入原来设元确认的 $j,k$ 值，即： $$i^{-1}\equiv -\left\lfloor{\dfrac{p}{i}}\right\rfloor(p\bmod i)^{-1}\pmod p$$ 显然，这时候我们要求出当前处理数 $i$（已知）时，唯一需要的值便是 $p\bmod i$ 的逆元。而不难发现该数是一定小于 $i$ 的（即 $p\bmod i<i$），那么我们可以认为该逆元是已知的，而前方的系数也容易求得。 于是我们得到了通式，即对于 $i=1$ 的情况逆元为 $1$，而对于 $i>1$ 的情况我们可以得到 $i^{-1}\equiv -\left\lfloor{\dfrac{p}{i}}\right\rfloor(p\bmod i)^{-1}\pmod p$。 由于一切在模 $p$ 意义下进行，所以存在 $-\left\lfloor{\dfrac{p}{i}}\right\rfloor=p-\left\lfloor{\dfrac{p}{i}}\right\rfloor$，通过这样我们可以避免负数的问题。 ```cpp #include<bits/stdc++.h> #define int long long using namespace std; int n,p,inv[20000530]; signed main(){ cin>>n>>p; inv[1]=1; for(int i=2;i<=n;++i) inv[i]=(p-p/i)*inv[p%i]%p; for(int i=1;i<=n;i++) cout<<inv[i]<<'\n'; return 0; } ``` 然而实现方法并不止这一种，在我们得到 $kj^{-1}+i^{-1}\equiv 0\pmod p$ 时就可以递归求得 $i^{-1}$ 的解，为了防止重复递归，我们可以使用记忆化方法，这样依然能够保证每个逆元只被求取一遍，复杂度仍旧是 $O(n)$。 至此，我们完成了线性求逆元的过程，即 $O(n)$ 求取 $1\sim n$ 的逆元。 ### 线性求任意逆元 其实要求任意给定的 $n$ 个数的逆元也很简单。 给定 $n$ 个数 $a_i$ 满足 $1\le a_i<p$，我们求出来 $n$ 个数的前缀积，也就是说对于任意的 $i\in[1,n]$，存在： $$s_i=\prod\limits_{x=1}^{n}a_i$$ 这时候我们可以用 Exgcd 或者快速幂法，在 $\log p$ 时间内求出来 $s_n$ 的乘法逆元，记为 $s_{inv_n}$。不难发现 $(a\times b)^{-1}=a^{-1}\times b^{-1}$，所以我们将 $s_n$ 乘以 $a_n$ 的时候，$a_n$ 就会和其逆元抵消掉。也就是说，我们可以通过这种方式求出 $s_{inv_{n-1}}$。 这样我们很容易依次求出所有前缀积的逆元 $s_{inv_{i}}$，而这让我们可以通过将前缀积的逆元乘上 $i-1$ 的前缀积以消除所有其他的逆元，这样我们就得到了 $a_i$ 的逆元，也就是说 $s_{i-1}\times sv_{i}=a_i^{-1}$。 代码实现： ```cpp s[0]=1; for(int i=1;i<=n;++i)s[i]=s[i-1]*a[i]%p; sv[n]=qpow(s[n],p-2); for(int i=n;i>=1;--i)sv[i-1]=sv[i]*a[i]%p; for(int i=1;i<=n;++i)inv[i]=sv[i]*s[i-1]%p; ``` 通过这样我们就在 $O(n+\log p)$ 这一接近线性的时间内完成了任意逆元的求取。 ## $\bold{Part\ 6\ 例题求解}$ ### [模板](https://www.luogu.com.cn/problem/P3811) 显然可以用递推法实现。 ```cpp #include<bits/stdc++.h> #define int long long using namespace std; int n,p,inv[20000530]={0,1}; signed main(){ cin>>n>>p; for(int i=2;i<=n;++i)inv[i]=(p-p/i)*inv[p%i]%p; for(int i=1;i<=n;i++)cout<<inv[i]<<endl; return 0; } ``` ### [同余方程](https://www.luogu.com.cn/problem/P1082) 显然可以用快速幂法进行求解，我们只需要将 $p-1$ 替换成 $\varphi(b)-1$ 就好啦。但是我们注意到 $b$ 的范围很大，所以不可能通过 $O(b)$ 方法进行筛除，我们考虑用单点求 $\varphi$。同时辅助快速幂进行实现即可。 ```cpp #include<bits/stdc++.h> #define int long long using namespace std; int a,b; int phi(int n){ int ans=1; for(int i=2;i*i<=n;i++){ if(n%i==0){ n/=i;ans*=(i-1); while(n%i==0)n/=i,ans*=i; } }if(n>1)ans*=(n-1); return ans; }int ksm(int base,int p){ int ans=1; while(p){ if(p&1)ans=ans*base%b; base=base*base%b; p>>=1; }return ans%b; }signed main(){ cin>>a>>b; int pb=phi(b); cout<<ksm(a,pb-1)%b<<endl; return 0; } ```