解决乘法逆元的三种方法

2019-04-14 15:27发布

站内文章 / 模拟电子
14574 0 933

1、拓展欧几里得#include #define ll long long using namespace std; ll n,p,x,y; void exgcd(ll a,ll b,ll &x,ll &y) { if(b==0){ x=1; y=0; return; } exgcd(b,a%b,x,y); ll temp=x; x=y; y=temp-(a/b)*y; } int main() { scanf("%d%d",&n,&p); for(int i=1;i<=n;++i){ exgcd(i,p,x,y); printf("%d ",(x%p+p)%p); } } 2、费马小定理#include #define ll long long using namespace std; ll n,p; void fmx(ll a,ll base,ll mod) { a%=mod; ll ans=1; while(base) { if(base%2)ans=(ans*a)%mod; a=(a*a)%mod; base>>=1; } printf("%lld ",ans); } int main() { scanf("%lld%lld",&n,&p); for(int i=1;i<=n;++i) fmx(i,p-2,p); }3、递推求线性逆元#include #define ll long long using namespace std; ll a[3000005]; ll n,p; int main() { scanf("%d%d",&n,&p); a[1]=1; printf("%d ",a[1]); for(int i=2;i<=n;++i) { a[i]=-(p/i)*a[p%i]; a[i]=(a[i]%p+p)%p; printf("%d ",a[i]); } }

热门文章