逆元

费马小定理（模数是质数）

long long power(long long a,long long b,long long c)
{
    a=a%c;
    long long res=1;
    while(b>0)
    {
        if(b&1) res=(res*a)%c;
        a=(a*a)%c;
        b=b>>1;
    }
    return res%c;
}
long long niyuan(long long a,long long b)//a在(mod b)意义下的逆元
{
    return power(a,b-2,b);
}

扩展欧几里得（gcd(a,b)|c）

int exgcd(int a,int b,long long &x,long long &y)
{
	if(b==0)
	{
		x=1;y=0;
		return a;
	}
	int d=exgcd(b,a%b,x,y);
	int tmp=x;
	x=y;
	y=tmp-(a/b)*y;
	return d;
} 
bool liEu(int a,int b,int c,long long &x,long long &y)
{
	int d=exgcd(a,b,x,y);
	if(c%d) return 0;
	int k=c/d;
	x*=k;y*=k;
	return 1;  
}
long long niyuan(long long a,long long b)
{
	int x=0,y=0;
	if(liEu(a,b,1,x,y))
	{
		return (x%b+b)%b;
	}
	return 0;
}

线性递推求(1~n)逆元P3811

#include<bits/stdc++.h>
using namespace std;
#define N 3000010
int n,p;
long long inv[N];
int main()
{
	scanf("%d%d",&n,&p);
	inv[1]=1;
	printf("1\n");
	for(int i=2;i<=n;++i)
	{
		inv[i]=1ll*(p-p/i)*inv[p%i]%p;
		printf("%lld\n",inv[i]);
	}
	return 0;
}

对于给出的n个数的快速求逆元,复杂度约为 $ O(n+log \ p) $

需要用到这个算法的题目:P5431，这题是个卡常哥，又卡时间又卡空间

{
	s[0]=1;
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
		s[i]=1ll*s[i-1]*a[i]%p;//前缀积 
	}
	sv[n]=niyuan(s[n],p);
	for(int i=n;i>=1;--i)
	{
		sv[i-1]=1ll*sv[i]*a[i]%p;//前缀商(前缀逆元) 
	}
	for(int i=1;i<=n;++i)
	{
		inv[i]=1ll*sv[i]*s[i-1]%p;
	}
}