线性求逆元

来自

要求线性内求出1-n中所有数的逆元((n<=3000000))
这时候(nlog(n))算法就有点悬了
所以需要一种(O(n))的算法
这个方法是这样的
首先(1^{-1} equiv 1 pmod p)
然后我们设(p = kcdot i + r,~r < i,~1 < i < p)
再将这个式子放到(mod p)意义下就会得到

[kcdot i + r equiv 0 pmod p ]

两边同时乘上(i^{-1}cdot r^{-1})就会得到

[kcdot r^{-1}+i^{-1}equiv 0pmod p ]

[i^{-1}equiv -kcdot r^{-1} pmod p ]

[i^{-1}equiv -leftlfloorfrac{p}{i} ight floorcdot left(pmod i ight)^{-1} pmod p ]

于是就可以从前面推出当前的逆元了，代码也就一行

A[i]=-(p/i)*A[p%i];

#include<iostream>
#include<cstdio>
#define N 3000005
using namespace std;

typedef long long ll;

ll _inv[N];  
void pre(int MOD){  
    _inv[0]=_inv[1]=1;  
    for(int i=2;i<N;i++)
        _inv[i]=((MOD-MOD/i)*_inv[MOD%i])%MOD;  
}    
int main(){  
    int n,p;
    cin>>n>>p;
    pre(p);
    for(int i=1;i<=n;++i)
    	printf("%d
",_inv[i]);
    return 0;  
}  

[ kcdot r^{-1} + i^{-1} &equiv& 0 &pmod p
i^{-1} &equiv& -kcdot r^{-1} &pmod p
i^{-1} &equiv& -leftlfloorfrac{p}{i} ight floorcdot left(pmod i ight)^{-1} &pmod p ]