P3811 【模板】乘法逆元

admin

https://www.luogu.org/problem/P3811


题目背景
这是一道模板题

题目描述
给定n,p求1~n中所有整数在模p意义下的乘法逆元。

输入格式
一行n,p

输出格式
n行,第i行表示i在模p意义下的逆元。

输入输出样例
输入
10 13
输出 1
7
9
10
8
11
2
5
3
4
说明1≤n≤3×10^6,n<p<20000528
输入保证 p 为质数。

admin

求逆元的方法很多，第一种是扩展的欧几里得算法（extGCD）

1. #include<iostream>
   
2. using namespace std;
   
3. typedef long long LL;
   
4. void extgcd(LL a,LL b,LL & d,LL & x,LL & y)
   
5. {
   
6.         if (b==0)        d=a,x=1,y=0; ///出口
   
7.         else
   
8.         {
   
9.                 extgcd(b,a%b,d,y,x);
   
10.                 y-=x*(a/b);  ///背下来吧
    
11.         }
    
12. }
    
13. int inv(int a,int p)
    
14. {
    
15.         LL d,x,y;
    
16.         extgcd(a,p,d,x,y);
    
17.         if (d==1) return (x+p)%p; ///这个很重要
    
18.         else return -1;
    
19. }
    
20. int main()
    
21. {
    
22.         int n,p;
    
23.         cin>>n>>p;
    
24.         for (int i=1; i<=n; i++)
    
25.                 cout<<inv(i,p)<<endl;
    
26.         return 0;
    
27. }

复制代码

admin

此题因为p是质数，所以任何n，都有gcd(n,p)=1;

Charleyxiao

线性求逆元
x^-1=-[p/x]*(p%x)^-1%p

1. #include<bits/stdc++.h>
   
2. #define int long long
   
3. using namespace std;
   
4. int n,p,inv[3000009];
   
5. signed main(){
   
6.         cin>>n>>p;
   
7.         inv[1]=1;
   
8.         puts("1");
   
9.         for(int i=2;i<=n;++i){
   
10.                 inv[i]=(p-p/i)*inv[p%i]%p;
    
11.                 printf("%lld\n",inv[i]);
    
12.         }
    
13.         return 0;
    
14. }

复制代码

Charleyxiao

设p=k*i+r
显然k*i+r=0(mod p)
同时乘上i^(-1),r^(-1)得k*r^(-1)+i^(-1)=0(mod p)
则i^(-1)=-k*r^(-1)(mod p)
得i^(-1)=-[p/i]*(p mod i)^(-1)(mod p)

Charleyxiao

[font face="黑体"]我是黑体字

罗汇翔

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. long long n,p;
   
4. long long ksm(long long a,long long b)
   
5. {
   
6.         long long ans=1;
   
7.         while(b)
   
8.         {
   
9.                 if(b%2)ans=ans*a%p;
   
10.                 a=a*a%p;
    
11.                 b=b/2;
    
12.         }
    
13.         return ans%p;
    
14. }
    
15. int main()
    
16. {
    
17.         cin>>n>>p;
    
18.         for(int i=1;i<=n;i++)cout<<ksm(i,p-2)<<endl;
    
19.         return 0;
    
20. }

复制代码