1.快速幂求法:
#include<cstdio>
using namespace std;
int qmi(int a, int k, int p){
int res = 1;
while(k){
if(k & 1) res = 1ll * res * a % p;
a = 1ll * a * a % p;
k >>= 1;
}
return res;
}
int main()
{
int n,p;
scanf("%d%d",&n,&p);
for(int i = 1;i <= n;i ++){
printf("%d\n",qmi(i, p - 2, p) % p); // 求 i 在 p 下的逆元
}
return 0;
}
2. 扩展欧几里得
#include<cstdio>
using namespace std;
void Exgcd(int a, int b, int &x, int &y) {
if (!b) x = 1, y = 0;
else Exgcd(b, a % b, y, x), y -= a / b * x;
}
int a,b;
int main() {
int x, y;
scanf("%d%d",&a,&b);
Exgcd (a, b, x, y);
x = (x % b + b) % b;
printf ("%d\n", x); //x是a在mod b下的逆元
}
3. 线性递推:
#include<bits/stdc++.h>
const int N = 3e6;
using namespace std;
int a[N],n,p;
int main(){
scanf("%d%d",&n,&p);
a[1]=1;
puts("1");
for(int i = 2;i <= n; i++){
a[i]=1ll * (p - p / i ) * a[p % i] % p;
printf("%d\n",a[i]);
}
}
```