素数を法とする世界の逆元をまとめて計算

　『整数xのmod pでの逆元を求めよ。』
と言われるとだいたい以下のいずれかの方法で解くと思います。

1. フェルマーの小定理を利用して、繰り返し二乗法でx^p-2を求める。
2. 拡張ユークリッドの互除法を使って、ax + py = 1という不定式を解く。

では、『整数[1, n)のmod pでの逆元を求めよ。』だとどうでしょうか？

この計算をO(n)でやる技を見かけたので、紹介します。（もしかしたら有名な技かもしれません。）

まずソースコードです。

#include <iostream>
#include <cassert>

using namespace std;

const long long MOD = 1e9+7;
const int N = 1e6;
long long inv[N];

int main(int argc, char **argv) {
    for (long long i = 1; i < N; i++) {
        inv[i] = (i == 1) ? 1 : (MOD - (MOD / i) * inv[MOD % i] % MOD);
        assert(inv[i] * i % MOD == 1);
    }
    cout << "success" << endl;
    
    return 0;
}

何をやっているか説明します。

今、整数aの逆元を求めたいとします。
つまり、ax = 1 (mod p)となるようなxが知りたいわけです。
ここで、(p % a) の逆元x'が分かっていたとします。
すると、
(p % a) x' = 1(mod p)
(p - p/a * a) x' = 1(mod p)
p * x' - p/a * a * x' = 1 (mod p)
-p/a * a * x'  = 1(mod p)   （∵ pが法なのでp * x' = 0）
a * (-p/a * x') = 1 (mod p)   (∵ 剰余群はアーベル群）
となり、
-p/a * x'、つまり、-p/a * inv(p % a)がaの逆元となります。

綺麗ですね。