#110. 乘法逆元
乘法逆元
内存限制：256 MiB时间限制：1000 ms标准输入输出
题目类型：传统评测方式：文本比较
上传者： Menci
题目描述
这是一道模板题。
给定正整数 n nn 与 p pp，求 1∼n 1 \sim n1∼n 中的所有数在模 p pp 意义下的乘法逆元。
输入格式
一行两个正整数 n nn 与 p pp
输出格式
n nn 行，第 i ii 行一个正整数，表示 i ii 在模 p pp 意义下的乘法逆元。
样例
样例输入
10 13样例输出
1
7
9
10
8
11
2
5
3
4数据范围与提示
1≤n≤3×106,n<p<20000528 1 \leq n \leq 3 \times 10 ^ 6, n < p < 200005281≤n≤3×106,n<p<20000528 p pp 为质数。
因为p是质数，所以我们很容易想到快速幂。
但是，
快速幂最后一个点会TLE
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 #include<algorithm>
7 #include<cstdlib>
8 #define lli long long int
9 using namespace std;
10 const lli MAXN=10001;
11 void read(lli &n)
12 {
13 char c='+';lli x=0,flag=1;
14 while(c<'0'||c>'9')
15 {c=getchar();if(c=='-')flag=-1;}
16 while(c>='0'&&c<='9')
17 {x=x*10+c-48;c=getchar();}
18 n=(x*flag);
19 }
20 lli n,mod;
21 lli fastpow(lli x,lli n)
22 {
23 lli ans=1;
24 for(;n;)
25 {if(n&1)ans=(ans*x)%mod;x=(x*x)%mod,n=n>>1;}
26 return ans;
27 }
28 int main()
29 {
30 read(n);read(mod);
31 for(lli i=1;i<=n;i++)
32 printf("%lld\n",fastpow(i,mod-2)%mod);
33 return 0;
34 } 然后看了一个大神的博客。
看到一个递推公式：
ans[i]=(mod-mod/i)*ans[mod%i]%mod;
虽然不知道什么意思但是应该是能非常快的推出逆元的，，
1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<queue>
6 #include<algorithm>
7 #include<cstdlib>
8 #define lli long long int
9 using namespace std;
10 const lli MAXN=10000001;
11 void read(lli &n)
12 {
13 char c='+';lli x=0,flag=1;
14 while(c<'0'||c>'9')
15 {c=getchar();if(c=='-')flag=-1;}
16 while(c>='0'&&c<='9')
17 {x=x*10+c-48;c=getchar();}
18 n=(x*flag);
19 }
20 lli n,mod;
21 int ans[MAXN];
22 int main()
23 {
24 read(n);read(mod);
25 ans[1]=1;
26 printf("1\n");
27 for(int i=2;i<=n;i++)
28 {
29 ans[i]=(mod-mod/i)*ans[mod%i]%mod;
30 printf("%d\n",ans[i]);
31 }
32 return 0;
33 } 本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-07-05 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录