快速幂求逆元与逆元

2024-05-26 11:36
文章标签 快速 逆元 幂求

本文主要是介绍快速幂求逆元与逆元,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

我上一篇博客链接写的是多个数求乘法逆元而快速幂求逆元用于单个数求乘法逆元

逆元是对分数取模用的

	对于除法取模不成立,即(a/b)%p≠(a%p/b%p)%p。求逆元的思路:(一般ACM的题目都是对1e9+7这种素数取模,所以gcd(a,p)==1)a*b=1(mod p) => b=1/a(mod p)。根据费马小定理:b^(p-1)=1(mod p) => b^(p-2)=1/b(mod p)可以看出来逆元1/b (mod p)=b^(p-2)可以得出a/b对质数p取模就是 a*b^(p-2) mod p 。

2024CCPC郑州邀请赛-Problem H. 随机栈用到了逆元但当时没有想到没有写出来

代码如下

#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
# define int long long
using namespace std;
int mod = 998244353;
map<int, int> m;
int asd(int a, int b) 
{int sum = 1;while(b){if(b%2==0){a=a*a%mod;b=b/2;}else{b=b-1;sum=sum*a%mod;b=b/2;a=a*a%mod;}}return sum%mod;
}
signed  main() {priority_queue<int, vector<int>, greater<int> > p;int n, num, l = -1, t = 0, s = 1, x = 1;cin >> n;for (int i = 0; i < 2 * n; i++) {cin >> num;if (t != 1){if (num == -1) {s = s * m[p.top()] % mod;x = x * p.size() % mod;if (p.top() >= l) {l = p.top();m[p.top()]--;p.pop();}elset = 1;} else {p.push(num);m[num]++;}}}if (t == 1)cout << "0" << endl;else {int ans = s * asd(x, mod - 2) % mod;cout << ans << endl;}}

这篇关于快速幂求逆元与逆元的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1004349

相关文章

hdu4828(卡特兰数+逆元)

这题的前几个数据分别为1,2,5,14,32......................然后确定这是个卡特兰数列 下面来介绍下卡特兰数,它的递推式为f[i+1] = f[i]*(4*n - 6)/n,其中f[2] = f[3] =1;f[4] = 2;f[5] = 14;f[6] = 32.................................. 但是这题的n太大了,所以要用到逆元,

电脑桌面文件删除了怎么找回来?别急,快速恢复攻略在此

在日常使用电脑的过程中,我们经常会遇到这样的情况:一不小心,桌面上的某个重要文件被删除了。这时,大多数人可能会感到惊慌失措,不知所措。 其实,不必过于担心,因为有很多方法可以帮助我们找回被删除的桌面文件。下面,就让我们一起来了解一下这些恢复桌面文件的方法吧。 一、使用撤销操作 如果我们刚刚删除了桌面上的文件,并且还没有进行其他操作,那么可以尝试使用撤销操作来恢复文件。在键盘上同时按下“C

hdu4869(逆元+求组合数)

//输入n,m,n表示翻牌的次数,m表示牌的数目,求经过n次操作后共有几种状态#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#includ

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

v0.dev快速开发

探索v0.dev:次世代开发者之利器 今之技艺日新月异,开发者之工具亦随之进步不辍。v0.dev者,新兴之开发者利器也,迅速引起众多开发者之瞩目。本文将引汝探究v0.dev之基本功能与优势,助汝速速上手,提升开发之效率。 何谓v0.dev? v0.dev者,现代化之开发者工具也,旨在简化并加速软件开发之过程。其集多种功能于一体,助开发者高效编写、测试及部署代码。无论汝为前端开发者、后端开发者

利用Django框架快速构建Web应用:从零到上线

随着互联网的发展,Web应用的需求日益增长,而Django作为一个高级的Python Web框架,以其强大的功能和灵活的架构,成为了众多开发者的选择。本文将指导你如何从零开始使用Django框架构建一个简单的Web应用,并将其部署到线上,让世界看到你的作品。 Django简介 Django是由Adrian Holovaty和Simon Willison于2005年开发的一个开源框架,旨在简

CentOs7上Mysql快速迁移脚本

因公司业务需要,对原来在/usr/local/mysql/data目录下的数据迁移到/data/local/mysql/mysqlData。 原因是系统盘太小,只有20G,几下就快满了。 参考过几篇文章,基于大神们的思路,我封装成了.sh脚本。 步骤如下: 1) 先修改好/etc/my.cnf,        ##[mysqld]       ##datadir=/data/loc

SAM2POINT:以zero-shot且快速的方式将任何 3D 视频分割为视频

摘要 我们介绍 SAM2POINT,这是一种采用 Segment Anything Model 2 (SAM 2) 进行零样本和快速 3D 分割的初步探索。 SAM2POINT 将任何 3D 数据解释为一系列多向视频,并利用 SAM 2 进行 3D 空间分割,无需进一步训练或 2D-3D 投影。 我们的框架支持各种提示类型,包括 3D 点、框和掩模,并且可以泛化到不同的场景,例如 3D 对象、室

UE5 半透明阴影 快速解决方案

Step 1: 打开该选项 Step 2: 将半透明材质给到模型后,设置光照的Shadow Resolution Scale,越大,阴影的效果越好

快速排序(java代码实现)

简介: 1.采用“分治”的思想,对于一组数据,选择一个基准元素,这里选择中间元素mid 2.通过第一轮扫描,比mid小的元素都在mid左边,比mid大的元素都在mid右边 3.然后使用递归排序这两部分,直到序列中所有数据均有序为止。 public class csdnTest {public static void main(String[] args){int[] arr = {3,