洛谷 P3811 【模板】乘法逆元 线性求逆元

https://www.luogu.com.cn/problem/P3811
洛谷 P3811 【模板】乘法逆元 线性求逆元

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn=3e6+5;

int n,p;
int inv[maxn]; //inv[i] 表示 i 模 p 的乘法逆元

void work()//求出 1-n 所有数在模 p 意义下的乘法逆元 要保证p是一个素数且 n<p
{
    inv[1]=1;
    for(int i=2;i<=n;i++)
    {
        inv[i]=(ll)-(p/i)*inv[p%i]%p;
        if(inv[i]<0)
            inv[i]+=p;
    }
}

int main()
{
    scanf("%d %d",&n,&p);
    work();
    for(int i=1;i<=n;i++)
        printf("%d\n",inv[i]);
    return 0;
}

洛谷 P3811 【模板】乘法逆元 线性求逆元洛谷 P3811 【模板】乘法逆元 线性求逆元 csu_xiji 发布了609 篇原创文章 · 获赞 23 · 访问量 3万+ 他的留言板 关注
上一篇:概率期望,数学,贪心策略——2020-camp-day1-A


下一篇:[题解] [Codechef] CNTL