三、乘法逆元
一、定义
若在mod p意义下,对于一个整数a,有a*b≡1(mod p),那么这个整数b即为a的 乘法逆元,同时a也为b的乘法逆元
一个数有逆元的充分必要条件是gcd(a,p)=1,此时a才有对p的乘法逆元
二、逆元是干什么的呢
首先对于除法取模不成立,即(a / b) % p 求取 (a/b)%p 等同于 求取 a∗(b的逆元)%p。 因此,求模运算的除法问题就转化为就一个数的逆元问题了。
另一个角度,不仅仅是为了除法取模。比如输入任意互质的两个数b,p,要使等式b%p=1恒成立,显然,要使等式恒成立必须借助一个数x(把这个数叫做b的逆元),使得bx%p==1
eg :b=22,p=5
显然22%5!=1
22*3%5==1,22的逆元x=3;
三、求取一个数的逆元,有两种方法
(1).费马小定理
因为在算法竞赛中模数p总是质数,所以可以利用费马小定理 :
bp−1%p=1
可以直接得到 b 的逆元是 bp−2, 使用 快速幂 求解即可
所以bp-2即为b在 mod p 意义下的逆元
ll pow(ll a, ll n, ll p) //快速幂 a^n % p { ll ans = 1; while(n) { if(n & 1) ans = ans * a % p; a = a * a % p; n >>= 1; } return ans; } ll niyuan(ll a, ll p) //费马小定理求逆元 { return pow(a, p - 2, p); }
(2)扩展欧几里德
对于利用拓展欧几里德算法求逆元,很显然,如果bx%p=1,那么 bx+py=1(p=0,解x),直接利用 exgcd(b, p, x, y),则 (x%p+p)%p 即为 b 的逆元((x%p+p)%p为x的最小正整数解)。
void exgcd(ll a, ll b, ll &x, ll &y) //拓展欧几里得算法 { if(!b) x = 1, y = 0; else { exgcd(b, a % b, y, x); y -= x * (a / b); } } ll niyuan(ll a, ll b) //求a对b取模的逆元 { ll x, y; exgcd(a, b, x, y); return (x + b) % b; }
模板题:https://www.cnblogs.com/-citywall123/p/10693865.html
来源https://blog.csdn.net/arrowlll/article/details/52629448
输入:
输入仅一行. 两个正整数a和n
输出:
输出仅一行. 一个正整数
样例解释:
((22)2)2mod 998244353 = 256
数据范围
a,n <= 1018
思路:
先求出指数,即 an-1(快速幂求解),并将指数对mod-1(因为mod是质数,那么φ(mod)= mod-1),再用更新后的指数做为新的指数用快速幂求解即可。
代码如下:
#include<cstdio> typedef long long ll; ll a,n; const int M=998244353; ll mi(ll a,ll b,int mod) { ll re=1; a%=mod; while (b) { if (b&1) re=(re*a)%mod; a=(a*a)%mod; b>>=1; } return re; } int main() { scanf ("%lld%lld",&a,&n); ll t=mi(a,n-1,M-1); printf("%lld",mi(a,t,M)); return 0; }
课后例题://poj 3696
L,L <= 2*109. 问多少个8连在一起的数是L的倍数。如果不存在就输出0.
//这里省略输入输出规则,请读者自行注意
思路:
x个8连在一起可以写成8*(10x-1)*9,假设d=gcd(L,8)。那么题目可以表达为:L | 8*(10x-1)*9 , 接下来我们做一些简单的式子变形:
L | 8*(10x-1)/9 ←→ L*9 | 8*(10x-1) ←→ 9L/d | (10x-1) ←→ 10x ≡ 1 (mod 9L/d)
引理:对于任意互质的正整数a,n,满足:ax≡1(mod n)最小的整数值 X0 是φ(n)的约数。
证明如下:
(反证法)假设X0不是φ(n)的约数,则φ(n)可以表示为:qX0 + r(0 <= r < X0)。题设有:aX0≡1(mod n),那么,aqX0≡1(mod n)且正整数a,n互质,所以有欧拉定理:
aφ(n)≡1(mod n),即aqX0 * ar≡1(mod n),继而得出:ar≡1(mod n),此时r<X0,这与X0是最小的整数值矛盾,所以假设不成立。得证。
φ(9L/d)并将其约数带入10x ≡ 1 (mod 9L/d)验证是否成立即可。求欧拉函数和快速幂,时间复杂度为:O(√(n) * log2 n)。代码如下:
#include<cstdio> #include<algorithm> using namespace std; typedef long long ll; ll n,mod; int Case; ll gcd(ll a,ll b) { return a%b==0 ? b : gcd(b,a%b); } ll Er(ll x) { ll re=x; for (ll i=2;i*i<=x;i++) { if (x%i==0) { re=re/i*(i-1); while (x%i==0) x/=i; } } if (x>1) re=re/x*(x-1); return re; } ll mul(ll a,ll b,ll p) { ll re=0; while (b) { if (b&1) re=(re+a)%p; a=2*a%p; b>>=1; } return re; } ll ksm(ll a,ll b,ll p) { ll re=1; a%=p; while (b) { if (b&1) re=mul(re,a,p); a=mul(a,a,p); b>>=1; } return re; } int main() { while (scanf ("%lld",&n)) { if (n==0) return 0; Case++; ll d=gcd(n,8); ll phi=Er(9*n/d); mod=9*n/d; ll flag=9223372036854775806; for (ll i=1;i*i<=phi;i++) { if (phi%i==0) { if (ksm(10,i,mod)==1) flag=min(flag,i); if (ksm(10,phi/i,mod)==1) flag=min(flag,phi/i); } } flag==9223372036854775806?printf("Case %d: 0\n",Case):printf("Case %d: %lld\n",Case,flag); } }
今天的文章乘法逆元_2的乘法逆元分享到此就结束了,感谢您的阅读,如果确实帮到您,您可以动动手指转发给其他人。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/51052.html