欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

求乘法逆元的几种姿势

程序员文章站 2022-07-07 19:39:53
...

luogu P3811 【模板】乘法逆元

题目背景

这是一道模板题

题目描述

给定n,p求1~n中所有整数在模p意义下的乘法逆元。

输入输出格式

输入格式:

 

一行n,p

 

输出格式:

 

n行,第i行表示i在模p意义下的逆元。

 

输入输出样例

输入样例#1: 复制
10 13
输出样例#1: 复制
1
7
9
10
8
11
2
5
3
4

说明

1 ≤ n ≤ 3*106, n < p < 20000528 1n3×106,n<p<20000528

输入保证 pp 为质数。

(1)快速幂+费马小定理(nlogp)[常数较大]

#include<cstdio>
#include<iostream>
#include<algorithm>
#define LL long long
#define FOR(i,s,t) for(register int i=s;i<=t;i++)
using namespace std;
int n,p;
inline LL Fast_Power(int a,int b){
    if(b==0)
        return 1;
    if(b==1)
        return a;
    LL ans=Fast_Power(a,b>>1);
    ans=(ans*ans)%p;
    return b&1?(ans*a)%p:ans; 
}
int main(){
    scanf("%d%d",&n,&p);
        FOR(i,1,n)
            printf("%lld\n",Fast_Power(i,p-2));
    return 0;
}

(2)exgcd求线性方程[常数较小]

#include<cstdio>
#include<iostream> 
#include<vector>
#include<algorithm>
#include<cmath>
#define BIG 100011 
#define ll long long
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
using namespace std;
ll ansx,ansy,n,p;
inline ll exgcd(ll a,ll b,ll &x,ll &y){
    if(!b)
        return a,x=1,y=0;
    ll s=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return s;
}
int main(){
    cin>>n>>p;
    FOR(i,1,n){
        exgcd(i,p,ansx,ansy);
        printf("%lld\n",(ansx+p)%p);
    }
    return 0;
} 

(3).线性算法O(n)

递推式 f[i]=p-p/i*f[p%i]%p.

 证明:

pΞk*i+r(mod p)

k*i+rΞ0(mod p)

同乘 i-1*r-1

k*r-1+i-1Ξ0 (mod p)

i-1Ξ-k*r-1(mod p)

f[i]=p-p/i*f[p%i]%p.

#include<cstdio>
#include<iostream> 
#include<vector>
#include<algorithm>
#include<cmath>
#define BIG 100011 
#define ll long long
#define FOR(i,s,t) for(register int i=s;i<=t;++i)
using namespace std;
ll n,p;
ll f[3000011];
int main(){
	cin>>n>>p;
	f[1]=1;
	puts("1");
	FOR(i,2,n){
		f[i]=(p-p/i)*f[p%i]%p;
		printf("%lld\n",f[i]);
	}
	return 0;
}