本文共 1394 字,大约阅读时间需要 4 分钟。
费马小定理求逆元
- 费马小定理:a是不能被质数p整除的正整数,则有 a^(p-1) ≡ 1 (mod p)求a关于p的乘法逆元,即为a*c≡ 1 (mod p),那么a^(p-2)就是a的逆元
- Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | LL quickpow(LL x,LL n,LL Mod){ LL ans=1; x%=Mod; while(n>0){ if(n&1) ans=(ans*x)%Mod; //n%2==1 x=(x*x)%Mod; n/=2; } return ans; } LL getInv(LL a,LL mod){ return quickpow(a,mod-2,mod); } //时间复杂度O(logMod),且当Mod为不能整除a的素数时可用,一般题目给出1e9+7; //当Mod-2过大的时候可以使用欧拉降幂防T,a^(Mod-2)%Mod=a^((Mod-2)%phi(Mod)+phi(Mod)) %Mod; |
扩欧求逆元
- 给定模数m,求a的逆相当于求解ax=1(mod m)这个方程可以转化为ax-my=1然后套用求二元一次方程的方法,用扩展欧几里得算法求得一组x0,y0和gcd检查gcd是否为1gcd不为1则说明逆元不存在若为1,则调整x0到0~m-1的范围中即可
- Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | LL exgcd(LL a,LL b,LL &x,LL &y)//扩展欧几里得算法 { if(b==0){ x=1,y=0; return a; } LL ret=exgcd(b,a%b,y,x); y-=a/b*x; return ret; } LL getInv(int a,int mod)//求a在mod下的逆元,不存在逆元返回-1 { LL x,y; LL d=exgcd(a,mod,x,y); return d==1?(x%mod+mod)%mod:-1; } //时间复杂度为O(logn),只要存在逆元均可求 |
线性推逆元
- 求1,2,…,N关于mod的逆元(mod为质数)
- Code
1 2 3 4 5 6 7 | const int mod = 1000000009; const int maxn = 10005; int inv[maxn]; inv[1] = 1; for(int i = 2; i < 10000; i++) inv[i] = inv[mod % i] * (mod - mod / i) % mod; //时间复杂度O(N),求1到N所有数的逆元 |
递归求逆元
- Code
1 2 3 4 5 6 | LL inv(LL i) { if(i==1)return 1; return (mod-mod/i)*inv(mod%i)%mod; } //O(logmod),mod是素数 |
转载地址:https://blog.csdn.net/cpongo3/article/details/89334336 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!