逆元

比较简单的前置知识。

1. 定义

$a*x =1\pmod b$，且 $\gcd(a,b)=1$，则我们称 $x$ 为 $a$ 的逆元，简称 $a^{-1}$。

然后我们在处理 $d/a\pmod b$，可以转化为 $d * a^{-1}\pmod p$。

2. 求法

1） 扩展欧几里得算法

可以转化为 $ax+by=1$，直接扩展欧几里得即可。

值得注意的是，我们要将 $x$ 变成 $[0,p-1]$ 的数。

typedef long long ll;
ll ExGCD(ll a,ll b,ll &x,ll &y){
	ll d;
    if(b==0) x=1,y=0,d=a;
    else
    {
		d=ExGCD(b,a%b,y,x),y-=a/b*x;
	}
	return d;
}

ll inv(ll a,ll p)// 求逆元的函数
{
    ll x,y;
    ExGCD(a,p,x,y);
    x=(x%p+p)%p;
    return x;
}

2）线性算法

首先，$1^{-1}=1$。

$[\dfrac{p}{i}]i+r=p\Leftrightarrow [\dfrac{p}{i}]i+r=0\pmod p$。

同时乘以 $i^{-1}r^{-1}$，就可以得到 $[\dfrac{p}{i}]r^{-1}+i^{-1}=0\pmod p$。

于是，$i^{-1}=-[\dfrac{p}{i}]*r^{-1}\pmod p$。

当然，这个也可以计算单个的逆元。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=5e6+10;
long long inv[N];

int main()
{
    int n,p;
    cin>>n>>p;
    inv[1]=1;
    for (int i=2;i<=n;++i) inv[i]=(p-(p/i))*inv[p%i]%p;
    for (int i=1;i<=n;++i) printf("%d\n",(inv[i]%p+p)%p);
    return 0;
}

3）快速幂

因为有费马小定理：$a^{p-1}=1\pmod p$，其中 p 为质数。

所以 $a*a^{p-2}=1\pmod p$。