#110. 乘法逆元
2018-06-17 22:17:22来源:未知 阅读 ()
#110. 乘法逆元
题目描述
这是一道模板题。
给定正整数 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×10?6??,n<p<20000528
p pp 为质数。
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 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 矩阵乘法(五):置换 2019-09-08
- 矩阵乘法(七):其它一些典型应用 2019-09-08
- 矩阵乘法(六):几何变换 2019-09-08
- 矩阵乘法(四):分析问题,确定递推式,采用矩阵快速幂求解 2019-09-04
- 矩阵乘法(三):根据要求构造矩阵进行快速幂运算 2019-09-04
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash