P3811 【模板】乘法逆元

题意

求1-n所有整数在模p意义下的逆元。

解法

A 拓展欧几里得算法

根据逆元的定义，即求解线性方程
\[ax=1(mod p)\]
转换一下也就是
\[ax+py=1\]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int extgcd(int a,int b,int&x,int&y){
    if(b==0){
        x=1;
        y=0;
        return a;
    }
    int g=extgcd(b,a%b,y,x);
    y-=a/b*x;
    return g;
}
int main(){
    int a,b,x,y;
    cin>>a>>b;
    for(int i=1;i<=a;i++){
        extgcd(i,b,x,y);
        cout<<(x%b+b)%b<<endl;
    }
}

得分：48。TLE

[洛谷P3811]【模板】乘法逆元

原文：https://www.cnblogs.com/water-lift/p/10427780.html