首页 > 代码库 > [蒟蒻修炼计划][学习笔记]数论(二)
[蒟蒻修炼计划][学习笔记]数论(二)
乘法逆元:若,则称
为
在
意义下的乘法逆元.
本文介绍乘法逆元的三种求法.
扩展欧几里得求逆元
因为,所以设
满足
,
则可以用扩展欧几里得求关于的方程
的一组解,即求出b.
inline int exgcd(int a,int b,int &x,int &y){ if(!b){ x=1;y=0;return a; } int ret=exgcd(b,a%b,y,x); y-=a/b*x;return ret;}inline int inver{ r=exgcd(a,p,b,q); if(r!=1) return -1; return b;}
费马小定理求逆元
因为,所以
,
则为a在
意义下的逆元.
typedef long long ll;inline ll power(ll x,ll k){ ll ret=1; while(k){ if(k&1) ret=ret*x%p; x=x*x%p;k>>=1; } return ret;}inline ll inver{ return power(a,p-2);}
线性求逆元
表示
在
(
为质数)意义下的逆元。
证明:因为,
所以
所以
所以
所以
typedef long long ll;inline ll inver{ re[1]=1; for(ll i=2,mul;i<=a;++i){ re[i]=-p/i*re[p%i]%p; if(re[i]<0){ mul=(0-re[i])/p+1; re[i]=(re[i]+mul*p)%p; } } return re[a];}
[蒟蒻修炼计划][学习笔记]数论(二)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。