首页 > 代码库 > #110. 乘法逆元

#110. 乘法逆元

2024-10-17 09:09:02   213人阅读

#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

样例输出

179108112534

数据范围与提示

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 为质数。

 
 
因为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 }
KSM

然后看了一个大神的博客。

看到一个递推公式：

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 }

 

#110. 乘法逆元


联系
我们