P3811 【模板】乘法逆元

阅读量：4671 次

发布时间：2019-06-09

本文共 1472 字，大约阅读时间需要 4 分钟。

回首望月一波之前\(logN\)求逆元的扩展欧几里得算法

（求解\(a * x \equiv 1(Mod\ p)\) \(\Leftrightarrow\) 求解 \(a * x + p * y = 1\)）

LL exgcd(LL a,LL b,LL &x,LL &y){//注意引用    if(!b){x = 1,y = 0;return a;}    int d = exgcd(b,a % b,x,y);    LL temp = x;x = y;y = temp - y * (a / b);    return d;    }    int main(){    a = RD();p = RD();    LL d = exgcd(a,p,x,y);    printf("%d\n",x);    return 0;    }

P3811 【模板】乘法逆元

题目背景

这是一道模板题

题目描述

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

输入输出格式

输入格式：

一行n,p

输出格式：

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

这次要求求出一串数的逆元之前的算法是\(nlogN\)的复杂度

但很显然承受不了，引入\(O(N)\)求一串逆元的方法（模数\(P\)为质数）

\[inv[1] = 1\]

\[inv[{i}] = ({P - P / i}) * inv[P\; \%\;i]\;\% P\]

Code

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          typedef long long LL;using namespace std;int RD(){ int out = 0,flag = 1;char c = getchar(); while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();} while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();} return flag * out; }const int maxn = 10000019;int a,p;LL x,y;LL exgcd(LL a,LL b,LL &x,LL &y){ if(!b){x = 1,y = 0;return a;} int d = exgcd(b,a % b,x,y); LL temp = x;x = y;y = temp - y * (a / b); return d; }//放个扩欧一起好了（才不是什么第一次扩欧TLE了呢）int inv[maxn];int main(){ a = RD();p = RD(); inv[1] = 1;printf("1\n"); for(int i = 2;i <= a;i++){ inv[i] = (LL)(p - p / i) * inv[p % i] % p; printf("%d\n",inv[i]); } return 0; }