题目背景
这是一道模板题
题目描述
给定n,p求1~n中所有整数在模p意义下的乘法逆元。
输入输出格式
输入格式：
一行n,p
输出格式：
n行,第i行表示i在模p意义下的逆元。
输入输出样例
输入样例#1：
10 13
输出样例#1：
1
7
9
10
8
11
2
5
3
4
说明
1 leq n leq 3 imes 10 ^ 6, n < p < 20000528 1≤n≤3×10
​6
​​ ,n //虽然加了ZlycerQan的各种骚优化 还是T掉一个点 #include #include #include using namespace std; typedef long long LL ; int n,p; inline void Fast_Pow(LL a,int b){ LL ret=1; while(b){ if(b&1) ret=(ret*a)%p; a=(a*a)%p,b>>=1; } printf("%lld ",ret); return ; } int Main(){ scanf("%d%d",&n,&p); for(register int i=1;i<=n;++i) Fast_Pow(i,p-2); return 0; } int Aptal_is_My_Son=Main(); int main(int argc,char *argv[]){ ; } AC代码： #include #include #include #include using namespace std; typedef long long LL ; const int MAXN = 3*1e6+5; LL inv[MAXN]; //线性求逆元 1->N Mod P 意义下的所有数对应的逆元值 //递推式：inv[i] = (P - P/i)*inv[P%i]%P;-----证明略 //inv[i]表示i在Mod P 意义下的逆元 void pre_inv(){ int p,n; inv[1]=1; cin>>n>>p; cout<<1<for(int i=2;i<=n;i++) inv[i]=(LL)(p-p/i)*inv[p%i]%p,printf("%lld ",inv[i]); } int main(){ pre_inv(); return 0; }