乘法逆元-线性算法

题目

https://www.luogu.com.cn/problem/P3811 给定 $n,p$ 求 $1\sim n$ 中所有整数在模 $p$ 意义下的乘法逆元。 这里 $a$ 模 $p$ 的乘法逆元定义为 $ax\equiv1\pmod p$ 的解。

思路

1. 费马小定理:逆元为$x=a^{p-2}\bmod p$
2. 扩展欧几里得算法:逆元为$x$
3. 线性算法

首先有$1^{-1}\equiv1(\bmod p)$,设$p=k*i+r,(1<r<i<p)$,$k$是商，$r$是余数$(r=p\bmod i)$,则$k*i+r\equiv0(\bmod p)$两边同时乘上$i^{-1},r^{-1}$得： $k*r^{-1}+i^{-1}\equiv0(bmod p)$，移项得$i^{-1}\equiv -k*r^{-1} (\bmod p)$ 因此$i^{-1}\equiv -\lfloor{\frac{p}{i}}\rfloor*(p\bmod i)^{-1} (\bmod p)$ 注意要开LL

代码

/**
⠀⠀⠀⠀⠰⢷⢿⠄
⠀⠀⠀⠀⠀⣼⣷⣄
⠀⠀⣤⣿⣇⣿⣿⣧⣿⡄
⢴⠾⠋⠀⠀⠻⣿⣷⣿⣿⡀
0   ⠀⢀⣿⣿⡿⢿⠈⣿
⠀⠀⠀⢠⣿⡿⠁⠀⡊⠀⠙
⠀⠀⠀⢿⣿⠀⠀⠹⣿
⠀⠀⠀⠀⠹⣷⡀⠀⣿⡄
⠀⠀⠀⠀⣀⣼⣿⠀⢈⣧
*/

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define debug(x) cout<<"a["<<x<<"]="<<a[x]<<endl;
#define pr(x) cout<<x<<endl;
#define ct(x) cout<<x<<" ";
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

typedef long long LL;
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;
const int N = 3e6 + 10;

int n,p;
LL nvi[N];

int main() {
    IOS;
#ifndef ONLINE_JUDGE
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.in", "r", stdin);
    freopen("/Users/houyunfei/CLionProjects/MyCppWorkSpace/test.out", "w", stdout);
#endif
    cin>>n>>p;
    nvi[1]=1;
    pr(1)
    for(int i=2;i<=n;i++){
        nvi[i]=(p-p/i)*nvi[p%i]%p;
        pr(nvi[i])
    }

    return 0;
}