快速幂极简写法快速幂求逆元

快速幂原理介绍

快速幂模板

int qmi(int a, int k, int p) {
	int res = 1;
	while (k) {
		//后面的a其实是底数与其指数的运算结果了,是不断迭代的
		//第一个a其实就是a的2的0次方
		if (k & 1) res = (res * a) % p;

		a = (a * a) % p;
		//注意,a是一个不断变化的过程
		//下一个a就等于上一个a的平方,
		
		k >>= 1;
	}
	return res;
}

快速幂求逆元

首先要知道什么是逆元。

在模运算下,如果存在一个数 b,使得 (a * b) mod p = 1,a不是p的倍数,那么我们称 b 是 a 在模 p 下的逆元。

费马小定理:假设我们需要计算 a 在模 p 下的逆元,即要找到一个数 b,使得 (a * b) mod p = 1。根据费马小定理,当 a 不是 p 的倍数时,有 a^(p-1) mod p = 1。将其变形为 a^(p-2) mod p = a^(-1) (mod p),即 a 的逆元(a^(-1))等于 a^(p-2) 在模 p 下的余数。因此,我们只需使用快速幂算法计算 a^(p-2) mod p 即可得到 a 在模 p 下的逆元。

例题:

分析:

1.先看逆元存不存在,不存在就输出impossible。如果a不是p的倍数(a%p!=0),逆元才存在。

2.如果逆元存在,用快速幂算 a^(p-2) mod p 即可

int qmi(int a, int k, int p) {
	int res = 1;
	while (k) {
		//后面的a其实是底数与其指数的运算结果了,是不断迭代的
		//第一个a其实就是a的2的0次方
		if (k & 1) res = (res * a) % p;

		a = (a * a) % p;
		//注意,a是一个不断变化的过程
		//下一个a就等于上一个a的平方,
		
		k >>= 1;
	}
	return res;
}

bool check(int a, int p) {
	if (a % p == 0) return true;
	
	return false;
}
signed main() {
	int t; cin >> t;
	while (t--) {
		int a, p; cin >> a >> p;
		if (check(a, p)) {
			cout << "impossible" << endl;
			continue;
		}
		cout << qmi(a, p - 2, p) << endl;

	}


	retu

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/173067.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

聊一聊Linux动态链接和GOT、PLT

共享动态库是现代系统的一个重要组成部分&#xff0c;大家肯定都不陌生&#xff0c;但是通常对背后的一些细节上的实现机制了解得不够深入。当然&#xff0c;网上有很多关于这方面的文章。希望这篇文章能够以一种与其他文章不同的角度呈现&#xff0c;可以对你产生一点启发。 …

【开源】基于Vue和SpringBoot的服装店库存管理系统

项目编号&#xff1a; S 052 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S052&#xff0c;文末获取源码。} 项目编号&#xff1a;S052&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 数据中心模块2.2 角色管理模块2.3 服…

什么是Jmeter ?Jmeter使用的原理步骤是什么?

1.1 什么是 JMeter Apache JMeter 是 Apache 组织开发的基于 Java 的压力测试工具。用于对软件做压力测试&#xff0c;它最初被设计用于 Web 应用测试&#xff0c;但后来扩展到其他测试领域。 它可以用于测试静态和动态资源&#xff0c;例如静态文件、Java 小服务程序、CGI 脚本…

Continuity” of stochastic integral wrt Brownian motion

See https://imathworks.com/math/math-continuity-of-stochastic-integral-wrt-brownian-motion/

5.基于飞蛾扑火算法(MFO)优化的VMD参数(MFO-VMD)

代码的使用说明 基于飞蛾扑火算法优化的VMD参数 优化算法代码原理 飞蛾扑火优化算法&#xff08;Moth-Flame Optimization&#xff0c;MFO&#xff09;是一种新型元启发式优化算法&#xff0c;该算法是受飞蛾围绕火焰飞行启发而提出的&#xff0c;具有搜索速度快、寻优能力强的…

梯度引导的分子生成扩散模型- GaUDI 评测

GaUDI模型来自于以色列理工Tomer Weiss的2023年发表在预印本ChemRxiv上的工作 《Guided Diffusion for Inverse Molecular Design》。原文链接&#xff1a;Guided Diffusion for Inverse Molecular Design | Materials Chemistry | ChemRxiv | Cambridge Open Engage GaUDI模型…

LeSS敏捷框架高效生产力实践

每个团队可能都有一套适合自己的敏捷方法&#xff0c;本文介绍了ResponseTap工程团队通过采用LeSS框架、引入准备周&#xff0c;从而提升迭代冲刺研发效能的实践。原文: LeSS Agile, More Productive — Part 1: Pain[1], LeSS Agile, More Productive — Part 2: Promise, LeS…

开源的进销存系统都有哪些?

开源的进销存系统有很多&#xff0c;以下是其中一些比较流行的: OpenERP&#xff1a;一个集成了多个业务功能的开源ERP软件&#xff0c;可以实现进销存管理&#xff0c;会计&#xff0c;仓库管理&#xff0c;销售管理等业务功能。 Odoo&#xff1a;是OpenERP的一个分支&#x…

【智能优化算法】从蚁群到动物园

目录 引言蚁群优化算法&#xff08;ACO&#xff09;ACO 机理ACO 模型描述ACO 移动策略 粒子群优化算法&#xff08;PSO&#xff09;PSO 机理PSO 模型描述 萤火虫群优化算法&#xff08;GSO&#xff09;GSO 机理GSO 模型描述 群智能优化算法 引言 21世纪&#xff0c;人类社会已经…

Python绘图库Plotly用超简单代码实现丰富的数据可视化图表

文章目录 前言Plotly 概述散点图时间序列分析 高级绘图功能散点图矩阵关系热图自定义主题 在 Plotly 图表工坊&#xff08;Plotly Chart Studio&#xff09;里编辑技术交流关于Python技术储备一、Python所有方向的学习路线二、Python基础学习视频三、精品Python学习书籍四、Pyt…

万字长文深入理解 cache,写出高性能代码

CACHE的一致性 Cache的一致性有这么几个层面 1. 一个CPU的icache和dcache的同步问题 2. 多个CPU各自的cache同步问题 3. CPU与设备&#xff08;其实也可能是个异构处理器&#xff0c;不过在Linux运行的CPU眼里&#xff0c;都是设备&#xff0c;都是DMA&#xff09;的cache同…

react等效memo的方法

视频教程 前端技术&#xff5c;Dan博客&#xff5c;在你写memo()之前_哔哩哔哩_bilibili 把与ExpensiveTree的无关的dom做成一个组件 第二种情况&#xff0c;color在ExpensiveTree组件的父级dom 创建一个组件&#xff0c;将state的color和input写上&#xff0c;而ExpensiveTr…

接入电商数据平台官方开放平台API接口获取商品实时信息数据,销量,评论,详情页演示

要接入电商数据平台官方开放平台API接口获取商品实时信息数据、销量、评论和详情页演示&#xff0c;需要按照以下步骤进行操作&#xff1a; 找到可用的API接口&#xff1a;首先&#xff0c;需要找到支持查询商品信息的API接口。可以在电商数据平台的官方开放平台上查找相应的AP…

springboot多环境配置

前言 在实际项目研发中&#xff0c;需要针对不同的运行环境&#xff0c;如开发环境、测试环境、生产环境等&#xff0c;每个运行环境的数据库…等配置都不相同&#xff0c;每次发布测试、更新生产都需要手动修改相关系统配置。这种方式特别麻烦&#xff0c;费时费力&#xff0…

n-皇后问题(DFS回溯)

n−皇后问题是指将 n 个皇后放在 nn的国际象棋棋盘上&#xff0c;使得皇后不能相互攻击到&#xff0c;即任意两个皇后都不能处于同一行、同一列或同一斜线上。 现在给定整数 n&#xff0c;请你输出所有的满足条件的棋子摆法。 输入格式 共一行&#xff0c;包含整数 n。 输出…

2023年【四川省安全员A证】复审考试及四川省安全员A证考试试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 四川省安全员A证复审考试根据新四川省安全员A证考试大纲要求&#xff0c;安全生产模拟考试一点通将四川省安全员A证模拟考试试题进行汇编&#xff0c;组成一套四川省安全员A证全真模拟考试试题&#xff0c;学员可通过…

Gitlab安装与操作

GitLab 是一个用于仓库管理系统的开源项目&#xff0c;使用Git作为代码管理工具&#xff0c;并在此基础上搭建起来的Web服务。 可通过Web界面进行访问公开的或者私人项目。它拥有与Github类似的功能&#xff0c;能够浏览源代码&#xff0c;管理缺陷和注释。可以管理团队对仓库的…

五年程序员兼职接单的肺腑之言

不知不觉我已经参加工作&#xff0c;当一个程序员五年了&#xff0c;从一个职场菜鸟逐渐变成老油条&#xff0c;个中辛酸只有自己知道。这五年做过各种兼职接单&#xff0c;踩过不少坑&#xff0c;今天就把我在程序员接单上的一些心得体会分享给大家&#xff0c;希望能对兼职接…

【每日OJ —— 225.用队列实现栈(队列)】

每日OJ —— 225.用队列实现栈&#xff08;队列&#xff09; 1.题目&#xff1a;225.用队列实现栈&#xff08;队列&#xff09;2.解法2.1.解法讲解&#xff1a;2.1.1.算法讲解2.1.2.代码实现2.1.3.提交通过展示 1.题目&#xff1a;225.用队列实现栈&#xff08;队列&#xff0…

Jieba库——中文自然语言处理的利器

中文作为世界上最广泛使用的语言之一&#xff0c;其复杂的结构和丰富的表达方式给中文文本处理带来了挑战。为了解决这些问题&#xff0c;Python开发者开发了一系列用于处理中文文本的工具和库&#xff0c;其中最受欢迎和广泛应用的就是Jieba库。Jieba是一个开源的中文分词工具…