在求1~N-1的逆元时，使用快速幂算法时时间复杂度为了O(nlog(n)) 但是在N超过1e6时也是一样的会超时， 所以俺就记录一个线性的算法来求1~N-1的逆元(O(n))；

其中N必为质数

推导:

公式推导：现在求k的逆元（k必须为质数
令a * k + b = p，
b ∗ inv[b] ≡ 1 (mod p)
(p − a * k) ∗ inv[b] ≡ 1 (mod p)
(p ∗ inv[b] − a * k ∗ inv[b]) ≡ 1 (mod p)N
因为 p ∗ inv[b] ≡ 0 (mod p)
得到 −a * k * inv[b] ≡ 1 (mod p)
又因为 b = p % kANDa * k + b = p,所以a=p/k(整除)
由b的表达式可以得到−a * k ∗ inv[p%k] ≡ 1 (mod p)
即−(p / k ) ∗ inv[p%k] ∗ k ≡ 1 (mod p)
所以有inv[k] = −(p/k) ∗ inv[p%k]
使用的时候加上p去掉负号

代码

int inv[N];
void ksm(int p)
{
    inv[1] = 1;
    for(int i = 2 ; i <= p - 1 ; i++)
    {
        inv[i] = (p-p / i) * inv[p % i] % p;
    }
}

练习

求逆元（模板）