Обратные элементы для всех чисел 1..n по простому модулю за O(n): откуда рекуррента?

Вывод чисто алгебраический. Пусть p простое, i — число от 2 до p-1. Запишем деление с остатком: p = (p / i)·i + (p mod i), где p / i — целая часть. Возьмём это равенство по модулю p (левая часть p ≡ 0):

0 ≡ (p/i)·i + (p mod i)   (mod p)

Теперь домножим всё на inv[i] · inv[p mod i] (обратные к i и к остатку):

0 ≡ (p/i)·inv[p mod i] + inv[i]   (mod p)

Отсюда:

inv[i] ≡ −(p/i)·inv[p mod i]   (mod p)

Поскольку p mod i < i, значение inv[p mod i] уже посчитано раньше — рекуррента «снизу вверх».

vector<long long> inverses(int n, long long p) {
    vector<long long> inv(n + 1);
    inv[1] = 1;
    for (int i = 2; i <= n; i++)
        inv[i] = (p - (p / i) * inv[p % i] % p) % p;
    return inv;
}

Знак минус заменён на (p - ...), чтобы остаток был неотрицательным. Сложность — O(n), против O(n log p) при наивном возведении каждого в степень. Требование: p простое и p > n.