洛谷 P3811 乘法逆元 题解
利用暴力快速幂O(nlogn)会TLE掉；
所以对于求1~n的所有逆元要用递推公式；
#include <bits/stdc++.h> using namespace std; long long inv[10000010]; int main () { int n,p; cin>>n>>p; inv[1]=1; cout<<inv[1]<<endl; for(register int i=2;i<=n;i++){ inv[i]=(p-p/i)*inv[p%i]%p; printf("%lld ",inv[i]); } }