当前位置: 首页 > news >正文

《洛谷深入浅出进阶篇》模意义下的乘法逆元+洛谷P3811

什么是乘法逆元?

算数意义上的乘法逆元指的是倒数,即:a*(1/a)=1


所以 1/a 是 a在算数意义下的乘法逆元,或者可以说二者互为逆元。
这有什么用呢?


除以a就等于乘上a的乘法逆元,乘以a等于除以a的乘法逆元。

那么我们回到我们要介绍的新的乘法逆元:模意义上的乘法逆元。(使用条件,当一个正整数做分母的时候)

例如我们要求(x+y)*(x-y)/2 mod p

很显然,对于分子,我们可以直接用模的性质
(x+y)*(x-y)modp = 【(x+y)%p *(x-y)%p】%p


但是,这样的方法只对加减乘有效。

除法的话,由于整除向下取整的原因,我们无法直接使用。这时候就要用到逆元,来代替除法,因为除以一个数取模,等于乘上它在模意义上的逆元,后取模。

ok,那么什么是模意义上的乘法逆元呢?


  给出定义: a*x = 1(mod)p,也就是a*x对p取模为1的时候,x就是a 的逆元,所以,当除以a的时候就相当于是乘上a的逆元x。(注意,模只对整数时有意义的,所以我们的变量都应该是整数)

那么我们知道了模意义上的乘法逆元,应该怎么求它的乘法逆元呢?
就可以用到三种方法:扩展欧几里得算法,费马小定理,线性递推。

扩展欧几里得算法:

a*x=1 (mod)p
这个式子可以展开写成:(扩展欧几里得相关文章连接:
《洛谷深入浅出进阶篇》 欧几里得算法,裴蜀定理,拓展欧几里得算法————洛谷P1516 青蛙的约会-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/louisdlee/article/details/134751119?spm=1001.2014.3001.5502
a*x+p*y=1
也就是求x,y的不定方程。
我们由裴蜀定理可知:这个方程只有gcd(a,p)=1的时候才有解,所以,gcd=1是求逆元的前提条件。

然后我们直接套exgcd(a,p,x,y)即可
虽然求出来的是a的一个逆元,但是我们由拓展欧几里得可以求出通式,x=x1+k*lcm(a,p)/a   (k可以取任意整数)

只要不断+模数p就可以求出最小正整数解

2,费马小定理:如果p是质数,且gcd(a,p)=1,a^(p-2)是a的一个乘法逆元。


那么如何求a^(p-2)?
我们可以用到快速幂的方法,

s=1,t=p-2   y=a
while(t!=0){
     if(p&1==1)s=s*y
     y*=y;
     t/=2;
}

线性递推求逆元


假如给你1~n个数,让你求所有整数在模p意义下的乘法逆元。你应该怎么办?(n<=1e6)

如果你每次都用exgcd或者费马小定理+快速幂这题是肯定是会超时的,所以我们只能用线性优化了。

只能使用递推的方式来解决这道题

那么我们必须找到递推的式子

假设 inv(i)是i在模意义下的逆元(记住板子即可)

p=i*q+r,其中q=【p/i】(整除),r=p%i。
第一个式子:p=i*q+r

在模意义下可以得到这样的式子:
 i*q+r == 0 (mod p)

变形为: i ==  -r/q  (mod p)

等价于:i== -r * inv(q)  (mod p)

两边取倒数:(整数的倒数来表示逆元函数)

1/i == -1/r   *   q

inv(i) == -inv(r)*q == -inv(r)*【p/i】;

因为 r=p%i,所以r是一定小于当前的i的,怎么求inv(r)

由于我们是递推求逆元,当求到i时,说明i-1,i-2,......1 都求出来了。

所以我们只要注意边界 inv(1) =1即可

但是还是有一个问题,就是,这样求出来的逆元,有些是负数的,如果我们要求逆元的最小正整数应该怎么办?
那也好办,不断在其后面加上p就可以了,当逆元大于0,退出循环。

上代码:

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#include<cctype>
#include<map>
#include<set>
#include<queue>
#include<numeric>
#include<iomanip>
using namespace std;
typedef long long LL;
const int N = 3e6 + 7;
LL inv[N];
int main()
{LL n,p;cin >> n>>p;inv[1] = 1;for (int i = 2; i <= n; i++) {LL q = p / i;LL r = p % i;inv[i] = (-q * inv[r]%p)%p;while(inv[i]<0)inv[i]+=p;}for (int i = 1; i <= n; i++)cout << inv[i] << '\n';
}


 

相关文章:

《洛谷深入浅出进阶篇》模意义下的乘法逆元+洛谷P3811

什么是乘法逆元&#xff1f; 算数意义上的乘法逆元指的是倒数&#xff0c;即&#xff1a;a*&#xff08;1/a&#xff09;1 所以 1/a 是 a在算数意义下的乘法逆元&#xff0c;或者可以说二者互为逆元。 这有什么用呢&#xff1f; 除以a就等于乘上a的乘法逆元&#xff0c;乘以…...

clickhouse -- clickhouse解析复杂JSON数组

举例 - 查数据 select _id,doctorId,patientId,diagnosisList from patient_disease final where diagnosisList is not null limit 3;- 解析数组 SELECT _id,doctorId,patientId,visitParamExtractRaw(diagnosisList,diagnosisName) FROM patient_disease final where _id …...

算法leetcode|91. 解码方法(rust重拳出击)

文章目录 91. 解码方法&#xff1a;样例 1&#xff1a;样例 2&#xff1a;样例 3&#xff1a;提示&#xff1a; 分析&#xff1a;题解&#xff1a;rust&#xff1a;go&#xff1a;c&#xff1a;python&#xff1a;java&#xff1a; 91. 解码方法&#xff1a; 一条包含字母 A-Z…...

zabbix配置snmp trap--使用snmptrapd和Bash接收器(缺zabbix_trap_handler.sh文中自取)--图文教程

1.前言 我的zabbix的版本是5.0版本&#xff0c;5.0的官方文档没有使用bash接收器的示例&#xff0c;6.0的官方文档有使用bash接收器的示例&#xff0c;但是&#xff0c;下载文件的链接失效&#xff1f;&#xff01; 这里讲解zabbix-server端配置和zabbix web端配置 2.zabbix-…...

vue: 线上项目element-ui的icon偶尔乱码问题

线上环境偶尔会复现&#xff0c; 具体&#xff1a; 一般使用不会出现这个问题&#xff0c;因为一般引入的是element-ui的css文件&#xff0c;问题出在于为了主题色变化啊&#xff0c;需要用到scss变量引入了scss文件。 import “~element-ui/packages/theme-chalk/src/index”…...

fpga rom 初始化文件的一些心得

目录 可能遇到的问题 问题 解决方案 rom的初始化 用途 文件类型 如何生成初始化文件 示例 Altera Xilinx 可能遇到的问题 问题 altera FPGA的rom找不到初始化文件&#xff0c;编译过程会提示类似的问题 Error(127001): Cant find Memory Initialization File or He…...

从零构建属于自己的GPT系列3:模型训练2(训练函数解读、模型训练函数解读、代码逐行解读)

&#x1f6a9;&#x1f6a9;&#x1f6a9;Hugging Face 实战系列 总目录 有任何问题欢迎在下面留言 本篇文章的代码运行界面均在PyCharm中进行 本篇文章配套的代码资源已经上传 从零构建属于自己的GPT系列1&#xff1a;文本数据预处理 从零构建属于自己的GPT系列2&#xff1a;语…...

Python词频统计(数据整理)

请编写程序&#xff0c;对一段英文文本&#xff0c;统计其中所有不同单词的个数&#xff0c;以及词频最大的前10%的单词。 输入格式: 输入给出一段非空文本&#xff0c;最后以符号#结尾。输入保证存在至少10个不同的单词。 输出格式: 在第一行中输出文本中所有不同单词的个数…...

基本面选股的方法

基本面选股是一种投资策略&#xff0c;主要关注公司的财务状况、盈利能力、行业地位等因素&#xff0c;以判断公司的价值并做出投资决策。以下是基本面选股的具体分析方法和重点&#xff1a; 财务状况分析&#xff1a; 利润表分析&#xff1a;关注公司的净利润、毛利率、营业…...

应用密码学期末复习(3)

目录 第三章 现代密码学应用案例 3.1安全电子邮件方案 3.1.1 PGP产生的背景 3.2 PGP提供了一个安全电子邮件解决方案 3.2.1 PGP加密流程 3.2.2 PGP解密流程 3.2.3 PGP整合了对称加密和公钥加密的方案 3.3 PGP数字签名和Hash函数 3.4 公钥分发与认证——去中心化模型 …...

PAD平板签约投屏-高端活动的选择

传统的现场纸质签约仪式除了缺乏仪式感之外还缺少互动性&#xff0c;如果要将签约的过程投放到大屏幕上更是需要额外的硬件设备成本。相比于传统的纸质签约仪式&#xff0c;平板现场电子签约的形式更加的新颖、更富有科技感、更具有仪式感。 平板签约投屏是应用于会议签字仪式的…...

分布式架构demo

1、外层创建pom 版本管理器 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.7.15</version><relativePath/> <!-- lookup parent from repository…...

TA-Lib学习研究笔记(二)——Overlap Studies上

TA-Lib学习研究笔记&#xff08;二&#xff09;——Overlap Studies 1. Overlap Studies 指标 [BBANDS, DEMA, EMA, HT_TRENDLINE, KAMA, MA, MAMA, MAVP, MIDPOINT, MIDPRICE, SAR, SAREXT, SMA, T3, TEMA, TRIMA, WMA]2.数据准备 get_data函数参数&#xff08;代码&#x…...

牛客java基础考点1 标识符和变量

牛客java基础考点1 标识符和变量 标识符 字母和数字&#xff1a; 标识符由字母、数字、下划线&#xff08;_&#xff09;和美元符号&#xff08;$&#xff09;组成。其中&#xff0c;标识符必须以字母、下划线或美元符号开头。大小写敏感&#xff1a; Java 是大小写敏感的语言…...

Qt将打印信息输出到文件

将打印信息&#xff08;qDebug、qInfo、qWarning、qCritial等&#xff09;输出到指定文件来以实现简单的日志功能。 #include "mainwindow.h" #include <QApplication> #include <QLoggingCategory> #include <QMutex> #include <QDateTime>…...

【risc-v】易灵思efinix FPGA sapphire_soc IP配置参数分享

系列文章目录 分享一些fpga内使用riscv软核的经验&#xff0c;共大家参考。后续内容比较多&#xff0c;会做成一个系列。 本系列会覆盖以下FPGA厂商 易灵思 efinix 赛灵思 xilinx 阿尔特拉 Altera 本文内容隶属于【易灵思efinix】系列。 前言 在efinix fpga中使用riscv是一…...

直播的种类及类型

随着网络技术和移动设备的普及&#xff0c;直播已经成为人们娱乐、学习、商业交流等众多领域的重要工具。 直播的种类主要有以下几种: 1.视频直播:这是最常见的直播形式&#xff0c;包括电商直播、婚庆直播、培训直播、家居直播等。 2.图文直播:这种直播形式包括PPT互动直播…...

时间序列数据压缩算法简述

本文简单介绍了时间序列压缩任务的来源&#xff0c;压缩算法的分类&#xff0c;并对常见压缩算法的优缺点进行了简介&#xff0c;爱码士们快来一探究竟呀&#xff01; 引言 时间序列数据是在许多应用程序和领域中生成的一种基本数据类型&#xff0c;例如金融、医疗保健、交通和…...

智能锁-SI522TORC522方案资料

南京中科微这款SI522目前完全PinTOPin兼容的NXP&#xff1a;RC522、CV520 复旦微&#xff1a;FM17520、FM17522/FM17550 瑞盟&#xff1a;MS520、MS522 国民技术:NZ3801、NZ3802 SI522 是应用于13.56MHz 非接触式通信中高集成度读写卡系列芯片中的一员。是NXP 公司针对&quo…...

redux(4) -RTK简单使用

简单使用 1、下载 npm i reduxjs/toolkit react-redux 2、创建 1、在redux/user.js中创建模块user。从reduxjs/toolkit中引入createSlice创建模块片段&#xff0c;我们需要传入name、初始数据initialState、改state的reducers等。最后需要导出reducer和action。 代码如下&a…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

AspectJ 在 Android 中的完整使用指南

一、环境配置&#xff08;Gradle 7.0 适配&#xff09; 1. 项目级 build.gradle // 注意&#xff1a;沪江插件已停更&#xff0c;推荐官方兼容方案 buildscript {dependencies {classpath org.aspectj:aspectjtools:1.9.9.1 // AspectJ 工具} } 2. 模块级 build.gradle plu…...

dify打造数据可视化图表

一、概述 在日常工作和学习中&#xff0c;我们经常需要和数据打交道。无论是分析报告、项目展示&#xff0c;还是简单的数据洞察&#xff0c;一个清晰直观的图表&#xff0c;往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server&#xff0c;由蚂蚁集团 AntV 团队…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

Git常用命令完全指南:从入门到精通

Git常用命令完全指南&#xff1a;从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...

Python实现简单音频数据压缩与解压算法

Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中&#xff0c;压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言&#xff0c;提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...