模意义下的乘法逆元

Albert_lob · 2025-07-29 21:58:55 · 个人记录

此题由于与P1082太过相同， 可以直接通过对P1082进行修改来AC，所以直接套用P1082的题解

#include<iostream>
using namespace std;
long long x,y;//这道题和同余方程差距不大，相当于求多个同余方程的值；
//因此没有弄更好的方式，用的是普通的同余方程法； 
void e(long long a,long long b){
    if(b==0){
        x=1;
        y=0;
        return;
    }
    e(b,a%b);
    long long tmp;
    tmp=x;
    x=y;
    y=tmp-a/b*y;
}
int main(){
    long long a,b;
    scanf("%lld%lld",&a,&b);
    for(int i=1;i<=a;i++){
        e(i,b);//时间复杂度差距不大； 
        x = (x % b + b) % b;
        printf("%d\n",x);
    }
    return 0;
}