ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 简单
  4. 正文

[模板]线性求逆元

2022年4月30日 1203点热度 0人点赞 0条评论

洛谷:P3811 【模板】乘法逆元 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

推导过程

保证 模数P 为一个质数。

代码 / code

/*Copyright (C) Eriktse 2022*/
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 3e6 + 9;

int inv[maxn];

void initInv(int N, int P,int a[])//a[]用于接收并操作inv数组 
{
	a[0] = a[1] = 1;//初始化 
	for(int i = 2;i <= N; ++ i)a[i] = (P - P / i) * a[P % i] % P;
}

signed main()
{
	int N, P;cin >> N >> P;
	initInv(N, P, inv);
	for(int i = 1;i <= N; ++ i)printf("%lld\n",inv[i]);
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ 模板 洛谷 算法 线性求逆元 逆元
最后更新:2022年7月9日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 推导过程
  • 代码 / code

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号