模板题: Luogu P3811 [模板] 乘法逆元
逆元类似于倒数,
在 ($mod$ $p$) 意义下, 如果 $a$*$inv$[$a$]≡ 1, 那么我们就说 $inv$[$a$]是 $a$ 的逆元,$a$ 也是 $inv$[$a$]的逆元.
前提必须保证 $a,p$ 互质.
当题目要求在 $mod$ $p$ 意义下求 $a*b$ 时, 为了避免数据过大引起的麻烦, 通常会把它拆成 $a$ $mod$ $p*b$ $mod$ $p$.
但是 $a/b$ 却不能这样拆分. 这时用逆元把它转化为 $a*inv$[$b$], 变成乘法, 就可以拆分了.
逆元的性质
1. 存在唯一性
2. 完全积性函数
$inv$[$a$]*$inv$[$b$] ≡ $inv$[$a*b$]
证明:
$a$*$inv$[$a$] ≡ $b$*$inv$[$b$] ≡ 1($mod$ $p$)
$a$*$inv$[$a$] * $b$*$inv$[$b$]≡ 1*1 ($mod$ $p$)
($ a $*$b$) * ($inv$[$a$]*$inv$[$b$]) ≡ 1 ($mod$ $p$)
3.
$a$*$inv$[$b$] ≡ $a/b$($mod$ $p$)
证明:
$b$*$inv$[$b$] ≡ 1 ($mod$ $p$)
同乘 $a/b$, 得
$a$*$inv$[$b$] ≡ $a/b$($mod$ $p$)
接下来介绍几种逆元的求法.
费马小定理
定理:$x$p-1 ≡ 1 ($mod$ $p$)
证明:(源自数论妙趣 -- 数学女王的盛情款待)
任意取一个质数, 比如 13. 考虑从 1 到 12 的一系列整数 1,2,3,4,5,6,7,8,9,10,11,12, 给这些数都乘上一个与 13 互质的数, 比如 3, 得到 3,6,9,12,15,18,21,24,27,30,33,36. 对于模 13 来说, 这些数同余于 3,6,9,12,2,5,8,11,1,4,7,10. 这些余数实际上就是原来的 1,2,3,4,5,6,7,8,9,10,11,12, 只是顺序不同而已.
把 1,2,3...12 统统乘起来, 乘积就是 12 的阶乘 12!. 把 3,6,9,..36 也统统乘起来, 并且提出公因子 3, 乘积就是 312*12!. 对于模 13 来说, 这两个乘积都同余于 1,2,3...12 系列, 尽管顺序不是一一对应, 即 312*12!≡12!mod 13. 两边同时除以 12! 得 312≡1 mod 13. 如果用 p 代替 13, 用 x 代替 3, 就得到费马小定理
$x$p-1≡1 ($mod$ $p$)
由 $x$p-1≡1 ($mod$ $p$)
得 $x$*$x$p-2≡1 ($mod$ $p$)
即 $x$p-2 是 $x$ 在 $mod$ $p$ 意义下的逆元
注意, 这个方法要求 $a,p$ 互质.
- int quickpow(int a,int b,int p){
- int ans = 1;
- int base = a;
- while(b){
- if(b&1)ans = ans*base % p;
- base = base*base % p;
- b>>= 1;
- }
- return ans%p;
- }
- int main(){
- scanf("%d%d",&n,&p);
- for(int i = 1;i <= n;i++)
- printf("%d\n",quickpow(i,p-2,p));
- return 0;
- }
扩展欧几里得
求 $a*x≡1$ ($mod$ $p$), 等同于
$a*x+p*y≡1$
我们知道,$exgcd$ 可求 $a*x + b*y≡gcd(a,b)$
而这里的 $a,p$ 互质, 刚好有 $gcd(a,p)=1$
所以求出 $exgcd(a,p,x,y)$,$inv[a] = x$
这个方法要比费马小定理快一点.
- void exgcd(int a,int b,int &x,int &y){
- if(b == 0){
- x = 1,y = 0;
- return;
- }
- exgcd(b,a%b,x,y);
- int tx = x;
- x = y;
- y = tx-(a/b)*y;
- }
- int main(){
- scanf("%d%d",&n,&p);
- for(int i = 1;i <= n;i++){
- exgcd(i,p,x,y);
- printf("%d\n",(x%p+p)%p);
- }
- return 0;
- }
线性推逆元
公式: inv[i]=inv[p%i]*(p-p/i)%p
证明:
令 $s=p/i,t=p$ $mod$ $i$,
则 $s*i+t=p$
$s*i+t≡0$ ($mod$ $p$)
$t≡-s*i$ ($mod$ $p$)
两边同除 $t*i$, 得
$t/(t*i)≡-s*i/(t*i)$ ($mod$ $p$)
$inv[i]≡-s*inv[t]$ ($mod$ $p$)
将 $s,p$ 的值带入, 则有
$inv[i]≡(-p/i)*inv[p$ $mod$ $i]$ ($mod$ $p$)
将 $-p/i$ 处理成正数, 即 $-p/i=p-p/i$
整理, 得 $inv[i]≡inv[p$ $mod$ $i]*(p-p/i)$ ($mod$ $p$)
这个方法很好, 适用于要求很多逆元的情况.
- inv[0] = inv[1] = 1;
- for(int i = 2; i <= n; i++)
- inv[i] = inv[p%i]*(p-p/i)%p;
[数论]逆元
来源: http://www.bubuko.com/infodetail-3004758.html