乘法逆元

洛谷-P3811-【模板】乘法逆元

快速幂

原理

见《进阶指南》第151页。

代码

#include <iostream>
using namespace std;

typedef long long LL;

int power (int a, int b, int p) {
    int res = 1 % p;
    while (b > 0) {
        if (b & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        b /= 2;
    }
    return res;
}

int main () {
    int n, p;
    scanf("%d%d", &n, &p);

    for (int i = 1; i <= n; ++ i)
        printf("%d\n", power(i, p - 2, p));
    return 0;
}

扩展欧几里得算法

原理

见《进阶指南》第151页。

代码

#include <iostream>
using namespace std;

int exgcd (int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }

    int d = exgcd(b, a % b, x, y);
    int copy_x = x, copy_y = y;
    x = copy_y, y = copy_x - copy_y * (a / b);
    return d;
}

int main () {
    int n, p;
    scanf("%d%d", &n, &p);

    for (int i = 1, x, y; i <= n; ++ i) {
        exgcd(i, p, x, y);
        printf("%d\n", (x % p + p) % p);
    }
    return 0;
}

线性求逆元

代码

#include <iostream>
using namespace std;

typedef long long LL;
const int N = 3000010;
int inv[N];

int main () {
    int n, p;
    scanf("%d%d", &n, &p);

    inv[1] = 1;
    for (int i = 2; i <= n; ++ i)
        inv[i] = (LL)(p - p / i) * inv[p % i] % p;

    for (int i = 1; i <= n; ++ i) printf("%d\n", inv[i]);
    return 0;
}