乘法逆元
2022/9/5 23:25:38
本文主要是介绍乘法逆元,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
乘法逆元
例题1
小凯的数字
\[2345=2\times 10^3+3\times 10^2+4\times 10^1+5\times 10^0\\ \forall x \geqq 0,10^x\mod 9=1\\ (2\times 10^3)\%9=(2\%9\times 10^3\%9)\%9=2\%9=2\\ 2345\%9=(2\times 10^3+3\times 10^2+4\times 10^1+5\times 10^0)\%9=(2+3+4+5)\%9=5\\ \therefore answer=[l+(l+1)+...+(r-1)+r]\%9=\frac{(l+r)(r-l+1)}{2}\%9 \]一串数字l(l+1)(l+2).......(r-1)r,例如l=2,r=5,数字为2345,小凯很喜欢数字9,所以写下的数字除以9的余数是多少
因为模运算必须是整数,上面的\((l+r)(r-l+1)\)可以用整数计算,除以2就不一定还是整数了。
那么分数在模意义下该怎么表示呢?也就是说在mod p意义下,能不能表示\(\frac{1}{a}\)呢?
在实数意义下,对于任意的\(a\neq 0\),都有\(a\times \frac{1}{a}=1\),所以在模意义下,也希望1/a也满足同样的性质:\(a\times \frac{1}{a}\equiv 1(\mod p)\),也就是说,尝试找到一个整数,满足\(a\times x\equiv 1(\mod p)\)
定义
若\(a\times x\equiv1(\mod p)\),则称x为a在模p意义下的乘法逆元,记为\(a^{-1}(\mod p)\)
在本章种,模意义下的乘法逆元,简称为逆元。
\[2\times 5\mod 9=10\mod 9=1\\ \therefore 5是2关于模9的逆元\\ 也就是说,\frac{1}{2}在模9的意义下可以用5来表示\\\\ 8\times \frac{1}{2}=4\\ 8\times 5\mod 9=40\mod 9=4\\ \]所以这题只需要求出\(5(l+r)(r-l+1)\mod9\) 为了降低处理的数量级,可以\(5(l+r)\%9(r-l+1)\%9\mod9\)
#include <bits/stdc++.h> using namespace std; int t; long long l,r,ans; int main() { cin>>t; while(t--){ cin>>l>>r; ans=((l+r)%9*(r-l+1)%9*5)%9; cout<<ans<<endl; } return 0; }
接下来,就从两种不同的方法给定一组a,p,求出a在模p意义下的逆元
方法1
拓展欧几里得算法
从\(a\times x\equiv1(\mod p)\)入手,等价于\(\exists y,ax+py=1\)等价。实际上就是一个关于a,p的不定方程,就可以用拓展欧几里得算法来解决
并且由裴蜀定理,可以发现存在a在模p意义下的逆元当且仅当gcd(a,p)=1,a和p互质,即\(a\perp p\)
int inv(int a,int p){ //用exgcd求逆元 int x,y; exgcd(a,p,x,y); //求不定方程ax+py=1的一组解 return x; //求出的x就是a在模p的意义下的乘法逆元 }
方法2
费马小定理
若p为质数,且a不是p的倍数,则\(a^{p-1}\equiv1(\mod p)\)
假设p为质数,那么如果a不是p的倍数,就有\(a\times a^{p-2}=a^{p-1}\equiv 1(\mod p)\)
所以a在模p意义下的逆元就是\(a^{p-2}\),可以用快速幂来解决。
如果a是p的倍数的话,对于任意x,ax也一定是p的倍数,不可能在模p的意义下等于1,也就不存在逆元了
int inv(int a,int p){ //用费马小定理求逆元 return pow(a,p-2,p); //求出a^(p-2)mod p的值 }
不管什么方法,都可以求出一个a在模p的意义下的逆元
定理
在大于等于0,小于p的范围内,模p的逆元(若存在)是唯一的
\[假设\exists 0\leq x_1<x_2<p,ax_1\equiv ax_2\equiv 1(\mod p)\\ 那么a(x_2-x_1)\equiv 0(\mod p)\\ \therefore a(x_2-x_1)是p的倍数\\ 又\because a\perp p\\ \therefore x_2-x_1是p的倍数\\ \because 0<x_2-x_1<p\\ \therefore x_2-x_1不是p的倍数,矛盾 \]例题2
乘法逆元(线性时间)
给定n,q,求1~n中所有整数在模p意义下的乘法逆元
递推
\[假设已经知道了1到i-1的逆元,现在要求i的逆元\\ 初始情况:当i=1时,i^{-1}\equiv 1(\mod p)\\ 2\leq i<p时\\ p=p/i\times i+p\%i\\ 同余式:p/i\times i+p\mod i\equiv0(\mod p)\\ \because p为质数,0<p\mod i<i\\ \therefore i和p\mod i的逆元一定存在\\ 在等式两边同时乘以i^{-1}(p\mod i)^{-1}\\ (p\mod i)^{-1}\times p/i+i^{-1}\equiv0(\mod p)\\ i^{-1}\equiv-(p\mod i)^{-1}\times p/l(\mod p) \]#include <bits/stdc++.h> using namespace std; int n,p; long long inv[3000010]; int main() { scanf("%d%d",&n,&p); inv[1]=1; //递推初始化 for(int i=2;i<=n;i++) inv[i]=(p-inv[p%i]*(p/i)%p); //i^(-1)=p-(p%i)^(-1)*(p/i)%p for(int i=1;i<=n;i++) printf("%lld\n",inv[i]); return 0; } //卡cin、cout
倒推
直接倒推可能会比较困难,但是我们知道\(\frac{1}{k}=\frac{(k-1)!}{k!}\),所以加入我们已经知道了1!,2!,...,n!mod p的结果,
并且已经知道了1!,2!,....,n!的逆元,就可以知道1到n的逆元了
\[1.用循环求出1!,2!,...,n!\mod p的结果\\ 2.用拓展那欧几里得算法/快速幂求出n!的逆元\\ 3.根据\frac{1}{(k-1)!}=\frac{k}{k!},倒推出(n-1)!,(n-2)!,...,1!的逆元\\ 4.根据\frac{1}{k}=\frac{(k-1)!}{k!},求出1到n的逆元\\ \]时间复杂度为O(n+log n)
#include <bits/stdc++.h> using namespace std; int n,p; long long inv[3000010],fac[3000010]; long long pow(long long x,int y,int p){ long long ans=1; for(;y;y>>=1){ if(y&1) ans=ans*x%p; x=x*x%p; } return ans; } int main() { scanf("%d%d",&n,&p); fac[0]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%p; //求出1!,2!,...,n! inv[n]=pow(fac[n],p-2,p); //求出(n!)^(-1) for(int i=n-1;~i;i--){ inv[i]=inv[i+1]*(i+1)%p; } //求出((n-1)!^(-1),(n-2)!^(-1),...,1!^(-1)) for(int i=1;i<=n;i++) printf("%lld\n",fac[i-1]*inv[i]%p); //求出1^(-1),2^(-1),...,n^(-1) return 0; }
这篇关于乘法逆元的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行
- 2024-05-08阿里云域名注册流程,分享给第一次购买域名的新手站长!