逆元inv

· · 个人记录

a \div b\%mod$不能拆分成两部分计算，于是就出现了乘法逆元，算出$b$关于$p$的乘法逆元，则原式变为$a \% mod \times inv(b) \% mod

以下方法采用扩展欧几里得算逆元：

#include<bits/stdc++.h>
#define ll long long
using namespace std;

inline void Exgcd(ll a, ll b, ll &x, ll &y) {
    if (not b) x = 1, y = 0;
    else Exgcd(b, a % b, y, x), y -= a / b * x;
}
int main() {
    ll x, y, n, p;
    scanf("%lld%lld", &n, &p);
    for(int i = 1; i <= n; i++) {
        Exgcd (i, p, x, y);
        x = (x % p + p) % p;
        printf ("%lld\n", x); 
    }
}

这里的x是a \% p的逆元