华师一附中OI组

标题: P3811 【模板】乘法逆元 [打印本页]
作者: admin    时间: 2019-10-23 20:29
标题: P3811 【模板】乘法逆元
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    时间: 2020-1-28 10:13
求逆元的方法很多，第一种是扩展的欧几里得算法（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    时间: 2020-1-28 10:16
此题因为p是质数，所以任何n，都有gcd(n,p)=1;
作者: Charleyxiao    时间: 2020-1-28 10:17
线性求逆元
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    时间: 2020-1-28 10:59
设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    时间: 2020-1-28 11:01
[font face="黑体"]我是黑体字
作者: 罗汇翔    时间: 2020-1-28 11:04
本帖最后由 罗汇翔 于 2020-1-28 11:10 编辑
  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. }
复制代码





欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2