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

lanqiaoOJ 4185：费马小定理求逆元

news 来源：原创 2025/7/5 22:54:36

【题目来源】
https://www.lanqiao.cn/problems/4185/learning/

【题目描述】
给出 n，p，求 $n^{-1} \ mod \ p$ 。其中， $n^{-1} \ mod \ p$ 指存在某个整数 0≤a<p，使得 na mod p=1，此时称 a 为 n 的逆元，即 $a=n^{-1}$ 。数据保证 p 是质数且 n mod p≠0。

【输入格式】
输入包含一行，为两个整数 n，p。

【输出格式】
输出包括一行，为一个整数，表示 $n^{-1} \ mod \ p$ 。

【输入样例】
3 5

【输出样例】
2

【说明】
3×2 mod 5=1，所以 $2=3^{-1}$ 。

【评测数据规模】
对于100%的评测数据，1≤n, p≤10^9+7。

【算法分析】
● 本题本质是求解同余方程 nx≡1(mod p) 的解。注意：题目中的 $n^{-1}$ 表示 n 的逆元，是一个表示符号，而不是数学中的 n 分之一。
● 由于 p 是质数且 gcd(n,p)=1，所以可以用费马小定理求解。在此约束下，特别是当模数 p 特别大的时候，由于快速幂的加持，更优先推荐使用费马小定理求逆元。

【算法代码】

#include <bits/stdc++.h>
using namespace std;typedef long long LL;LL fastPow(LL a,LL n,LL p) {LL ans=1;while(n) {if(n & 1) ans=ans*a%p;n>>=1;a=a*a%p;}return ans%p;
}int main() {LL n,p;cin>>n>>p;cout<<fastPow(n,p-2,p);return 0;
}/*
in:3 5
out:2
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/148008443
https://blog.csdn.net/hnjzsyjyj/article/details/147980706

相关文章：

lanqiaoOJ 4185：费马小定理求逆元

【题目来源】 https://www.lanqiao.cn/problems/4185/learning/ 【题目描述】给出 n，p，求。其中， 指存在某个整数 0≤a<p，使得 na mod p1，此时称 a 为 n 的逆元，即。数据保证 p 是质数且 n mod p≠0…...

编程日记 2025/7/5 22:54:36

计算机视觉与深度学习｜ Python实现CEEMDAN-ISOS-VMD-GRU-ARIMA时间序列预测（完整源码和数据)

以下是结合CEEMDAN、ISOS-VMD、GRU和ARIMA的时间序列预测的Python完整实现方案。本方案包含完整的代码、数据生成逻辑和实现细节说明。完整代码实现 import numpy as np import pandas as pd from PyEMD import CEEMDAN from vmdpy import VMD from scipy.optimize import di…...

编程日记 2025/7/3 19:51:51

前端开发遇到 Bug，怎么办？如何利用 AI 高效解决问题

前端开发遇到 Bug，怎么办？如何利用 AI 高效解决问题作为前端开发者，遇到 Bug 几乎是日常。无论是样式错乱、功能异常，还是接口数据不对，Bug 总能让人头疼。但随着人工智能（AI）技术的发展&…...

编程日记 2025/7/5 14:25:11

博主总结框架

1.博主总结框架 1.1 计算机基础类（数据结构、计算机网络、操作系统等） （1）数据结构 （2）操作系统 （3）计算机网络 （4）其他物联网入门框架 1.2 计算机图形…...

编程日记 2025/7/5 22:26:52

国产化Excel处理组件Spire.XLS for .NET系列教程：通过 C# 将 TXT 文本转换为 Excel 表格

在数据处理和管理场景中，将原始文本文件（TXT）高效转换为结构化的 Excel 电子表格是一项常见要求。对于那些需要自动生成报表或者处理日志文件的开发人员而言，借助 C# 实现 TXT 到 Excel 的转换工作，可以简化数据组织和…...

编程日记 2025/7/5 21:53:02

网络安全--PHP第一天

目标熟悉信息传递架构基于phpstydy-mysql-php 前置条件需要先在数据库中创建相应的库和表名并配置表的结构该文件为数据库配置文件名字为config.php <?php $dbip localhost;//连接数据库的地址远程连接需要输入ip等 $dbuser root;//连接数据库的用户 $dbpass ro…...

编程日记 2025/7/5 22:40:34

结构型：组合模式

目录 1、核心思想 2、实现方式 2.1 模式结构 2.2 实现案例 3、优缺点分析 4、适用场景 1、核心思想目的：将总是在重复、迭代地显示的某种自相似性的结构（部分与整体结构特征相似），例如树形结构，以统一的方式处…...

编程日记 2025/6/27 23:23:07

Node.js多版本安装工具NVM详细使用教程

一、nvm 简介 nvm（Node Version Manager）是一个用于管理多个 Node.js 版本的命令行工具，允许开发者在单个系统中轻松切换、安装和卸载不同版本的 Node.js。它是前端和后端开发中处理 Node.js 版本兼容性问题的核心工具之一。二、nvm 安装 …...

编程日记 2025/6/27 23:01:26

深度解析 Java 中介者模式：重构复杂交互场景的优雅方案

一、中介者模式的核心思想与设计哲学在软件开发的历史长河中，对象间的交互管理一直是架构设计的核心难题。当多个对象形成复杂的网状交互时，系统会陷入 "牵一发而动全身" 的困境。中介者模式（Mediator Pattern）作为行…...

编程日记 2025/6/27 22:57:43

（八）深度学习---计算机视觉基础

分类问题回归问题聚类问题各种复杂问题决策树√线性回归√K-means√神经网络√逻辑回归√岭回归密度聚类深度学习√集成学习√Lasso回归谱聚类条件随机场贝叶斯层次聚类隐马尔可夫模型支持向量机高斯混合聚类LDA主题模型一.图像数字化表示及建模基础二.卷积神经网络CNN基本原…...

编程日记 2025/6/29 8:33:14

深入剖析原型模式：原理、实现与应用实践

在软件开发的世界里，设计模式如同建筑师手中的蓝图，为复杂系统的构建提供了行之有效的解决方案。其中，原型模式（Prototype Pattern）作为创建型设计模式的重要一员，以其独特的对象创建方式，在提高代码复用性、增强系统灵活性等方面发挥着关键作用。本文将深入剖析原型模式…...

编程日记 2025/6/27 23:25:59

【论文阅读 | CVPR 2024 |RSDet:去除再选择：一种用于 RGB - 红外目标检测的由粗到精融合视角】

论文阅读 | CVPR 2024 |RSDet:去除再选择：一种用于 RGB - 红外目标检测的由粗到精融合视角 1.摘要&&引言2. 方法2.1 “由粗到细”融合策略2.2 冗余光谱去除模块（RSR）2.3 动态特征选择模块（DFS）2.4 去除与选择检…...

编程日记 2025/6/27 23:35:00

WinForms 应用中集成 OpenCvSharp 实现基础图像处理

引言欢迎关注dotnet研习社，今天我们要讨论的主题是WinForms 应用中集成 OpenCvSharp 实现基础图像处理。在常规的图像处理软件开发中，图像处理功能是这些应用程序的核心组成部分。无论是简单的照片编辑工具，还是复杂的计算机视觉应用&…...

编程日记 2025/6/27 23:16:49

apache http client连接池实现原理

在java开发中我们经常会涉及到http 请求接口，一般有几种方式： java自带的 HttpURLConnectionokHttpClientapache http client 一般我们使用apache http client会比较多点，在代码中会进行如下调用方式： private static class Htt…...

编程日记 2025/6/27 23:19:43

adb抓包

目录抓包步骤步骤 1: 获取应用的包名步骤 2: 查看单个应用的日志步骤 3: 使用日志级别过滤器步骤 4: 高级日志过滤可能的原因： 解决方案： 额外提示： 日志保存抓包步骤连接设备 adb devices 步骤 1: 获取应用的包名首先…...

编程日记 2025/6/27 22:58:50

C语言---结构体、联合体、枚举

一、初识结构体 1、结构体类型结构体和数组都是集合，但是结构体有成员，类型可以不同；数组有成员，类型相同。 int main() {struct tag{member--list //一个或者多个成员，成员变量}variable--list;//可以省略&#x…...

编程日记 2025/6/27 23:20:08

Web Workers 使用指南

文章目录前言基础使用高级特性使用 ES Modules实际应用场景图像处理大数据处理轮询任务性能优化技巧现代开发方式使用 worker-loader (Webpack) Vite中的Worker使用限制与注意事项DOM限制:通信限制:同源策略:最佳实践前言 Web Workers 是浏览器提供的 JavaScript 多线程解…...

编程日记 2025/6/27 23:19:23

JVM 与容器化部署调优实践（Docker + K8s）

📌 文章目录 📘 前言1️⃣ 容器环境下 JVM 面临的新挑战2️⃣ JVM 的容器资源感知机制详解3️⃣ JVM 内存调优：如何正确使用堆内存4️⃣ JVM CPU 调优：GC 与编译线程控制5️⃣ Kubernetes 典型配置误区与对策6️⃣ 实战案例&#…...

编程日记 2025/6/27 23:37:56

Android OkHttp控制链：深入理解网络请求的流程管理

OkHttp作为Android和Java平台上广泛使用的HTTP客户端，其核心设计之一就是"控制链"(Chain)机制。本文将深入探讨OkHttp控制链的工作原理、实现细节以及如何利用这一机制进行高级定制。一、什么是OkHttp控制链 OkHttp控制链是一种责任链模式的实现&#…...

编程日记 2025/6/27 23:13:40

《易经》的数学表达：初级版和高级版

《易经》的数学表达， 一、初级版，可基于以下框架构建， 涵盖符号系统、结构代数及变换规则： 此框架将《易经》抽象为离散数学结构，兼容符号逻辑、概率论与群论，为算法化占断、卦象拓扑分析及跨文化比较提供…...

编程日记 2025/6/27 23:25:20

卷积神经网络基础（十）

之前我们学习了SGD、Momentum和AdaGrad三种优化方法，今天我们将继续学习Adam方法。 6.1.6 Adam 我们知道Momentum参照的是小球在碗中滚动的物理规则进行移动而实现的，AdaGrad为参数的每个元素适当地调整更新步伐。那如果我们将这两种方法融合在一起会不…...

编程日记 2025/6/27 23:18:02

怎么把cursor（Cursor/ollama）安装到指定路径

使用PowerShell命令打开电脑开始菜单，输入powerShell，使用管理员权限打开powerShell窗口，使用cd命令到cursor或ollama安装包的下载目录，如我的Cursor所在的目录为D:\environment\cursor\soft，输入以下 cd E:\downloa…...

编程日记 2025/6/27 23:18:54

第21天-pyttsx3语音播放功能

示例1：语音参数控制（语速/音量/音调） import pyttsx3def speech_demo():engine = pyttsx3.init()# 获取当前语音参数print("默认语速:", engine.getProperty(rate))print("默认音量:", engine.getProperty(volume))print("可用语音:", engin…...

编程日记 2025/6/27 20:49:02

Multi-Query Attention：传统自注意力（ Self-Attention）优化显存和加速方案

本文导读：Multi-Query Attention（MQA）是 Google Research 2022 年提出的一项轻量化注意力技术，通过“多查询、单键值”的设计，把自注意力层的 KV 缓存从 O(hnd) 降到 O(nd)，在不牺牲模型精度的前提下大幅节…...

编程日记 2025/6/27 23:03:45

学习路之uniapp--unipush2.0推送功能--服务端推送消息

学习路之uniapp--unipush2.0推送功能--服务端推送消息一、二、三、一、二、三、...

编程日记 2025/7/5 0:10:44

如何使用AI搭建WordPress网站

人工智能正迅速成为包括网页设计在内的许多行业在其功能设置中添加的一种工具。在数字设计和营销领域，许多成熟的工具都在其产品中添加了人工智能功能。WordPress 也是如此。作为目前最流行的网站建设工具之一，WordPress 的人工智能插件越来越多也就不足…...

编程日记 2025/6/27 23:07:23

Java 项目管理工具：Maven 与 Gradle 的深度对比与选择

Java 项目管理工具：Maven 与 Gradle 的深度对比与选择在 Java 开发领域，项目管理工具对于项目的构建、依赖管理等起着至关重要的作用。Maven 和 Gradle 是目前最主流的两款工具，它们各自有着独特的优势和适用场景。本文将对 Maven 与 Gradl…...

编程日记 2025/6/27 23:35:50

Elasticsearch简单集成java框架方式。

Elasticsearch 在 Java 中最常用的客户端是什么？如何初始化一个 RestHighLevelClient？如何用 Spring Boot 快速集成 Elasticsearch？Spring Data Elasticsearch 如何定义实体类与索引的映射？ 最常用的 Java 客户端目前官方推荐使用…...

编程日记 2025/6/27 23:00:54

50天50个小项目 (Vue3 + Tailwindcss V4) ✨ | Hidden Search Widget （交互式搜索框）

📅 我们继续 50 个小项目挑战！—— Hidden Search Widget 组件仓库地址：https://github.com/SunACong/50-vue-projects 项目预览地址：https://50-vue-projects.vercel.app/ ✨ 组件目标点击按钮展开隐藏的搜索框再次点击按钮…...

编程日记 2025/6/27 23:30:48

python爬虫和逆向：百度翻译数据采集的几种方式

更多内容请见：爬虫和逆向教程-专栏介绍和目录文章目录一、官方API方式（推荐）1.1 百度翻译开放平台API二、网页版逆向方式（代码可直接运行）2.1 拿到js加密方法2.2 python解密代码三、浏览器自动化方式3.1 Selenium自动化操作3.2 Playwright自动化四、移动端API逆向4.1 分…...

编程日记 2025/6/27 23:13:59

spring5-配外部文件-spEL-工厂bean-FactoryBean

spring配外部文件我们先在Spring里配置一个数据源 1.导c3p0包,这里我们先学一下hibernate持久化框架，以后用mybites. <dependency><groupId>org.hibernate</groupId><artifactId>hibernate-core</artifactId><version>5.2.…...

编程日记 2025/7/5 16:33:10

Ubuntu部署私有Gitlab

这个东西安装其实挺简单的，但是因为我这边迁移了数据目录和使用自己安装的 nginx 代理还是踩了几个坑，所以大家可以注意下先看下安装 # 先安装必要组件 sudo apt update sudo apt install -y curl openssh-server ca-certificates tzdata perl# 添加gi…...

编程日记 2025/6/27 23:07:27

Activiti 7建表语句及注释

Activiti数据库表Oracle兼容DM建表语句及字段注释。附件下载版地址点这里 --通用属性表 create table ACT_GE_PROPERTY (NAME_ NVARCHAR2(64),VALUE_ NVARCHAR2(300),REV_ INTEGER,primary key (NAME_) );COMMENT ON TABLE ACT_GE_PROPERTY IS 通用属性表;COMMENT ON COLUMN …...

编程日记 2025/6/27 23:20:15

React中使用 Ant Design Charts 图表

// 引入 Ant Design Charts 的柱状图组件 Column import { Column } from ant-design/charts;// 定义函数组件 App，用于展示柱状图 function App() {// 数据源：每个对象代表一个柱子，包含类型（type）和销售额&#xff0…...

编程日记 2025/6/27 23:14:04

佰力博科技与您探讨压电材料的原理与压电效应的应用

压电材料的原理基于正压电效应和逆压电效应，即机械能与电能之间的双向转换特性。压电材料的原理源于其独特的晶体结构和电-机械耦合效应，具体可分为以下核心要点： 1. ‌正压电效应与逆压电效应的定义‌ ‌正压电效应‌：当压电…...

编程日记 2025/6/27 23:22:05

vscode打开vue + element项目

好嘞，我帮你详细整理一个用 VS Code 来可视化开发 Vue Element UI 的完整步骤，让你能舒服地写代码、预览界面、调试和管理项目。用 VS Code 可视化开发 Vue Element UI 全流程指南一、准备工作安装 VS Code 官网下载安装：https://code…...

编程日记 2025/6/27 22:57:51

一步步解析 HTTPS

🧑 博主简介：CSDN博客专家，历代文学网（PC端可以访问：https://literature.sinhy.com/#/literature?__c1000，移动端可微信小程序搜索“历代文学”）总架构师，15年工作经验，…...

编程日记 2025/6/27 23:26:30

使用vue2做一个生成二维码的案例【可当组件使用】

最近有个需求需要用前端来生成一个二维码，就封装了一个简单的组件，这篇文章来分享给大家。使用的技术： Vue2 Ant Design Vue QRCodeJS2 node版本：16.20 组件样式： 大家可以根据自己的需求来调整代码。依赖安装&am…...

编程日记 2025/6/27 23:27:03

Hadoop-HA高可用集群启动nameNode莫名挂掉，排错解决

Hadoop-HA高可用集群启动nameNode莫名挂掉，排错解决 nameNode错误日志 2025-05-21 16:14:12,218 INFO org.apache.hadoop.ipc.Client: Retrying connect to server: node01/192.168.191.111:8485. Already tried 5 time(s); retry policy is RetryUpToMaximumCoun…...

编程日记 2025/6/27 22:57:52

从零基础到最佳实践：Vue.js 系列（2/10）：《模板语法与数据绑定》

Vue.js 模板语法与数据绑定：从基础到实践关键点 Vue.js 的模板语法使用 HTML 结合特殊指令（如 v-bind、v-on），实现动态界面。插值（{{ }}）显示数据，指令控制 DOM 行为，双向绑定简化…...

编程日记 2025/6/27 23:38:43

第二章：Android常用UI控件

1、介绍： 控件是界面组成的主要元素，界面中的控件有序排放和完美组合，便可在用户眼前呈现出丰富多彩的页面。 2、常用控件： 一、TextView控件： 在使用手机时，经常会看见一些文本信息，这些文本…...

编程日记 2025/6/27 23:01:17

LeetCode 1004. 最大连续1的个数 III

LeetCode 1004题 “最大连续1的个数 III” 是一道关于数组和滑动窗口的问题。题目描述如下： 题目描述给定一个由若干 0 和 1 组成的数组 nums，以及一个整数 k。你可以将最多 k 个 0 翻转为 1。返回经过翻转操作后，数组中连续 1 的最大个数…...

编程日记 2025/6/27 23:24:03

Flink CDC 3.4 发布, 优化高频 DDL 处理，支持 Batch 模式，新增 Iceberg 支持

引言 Apache Flink 社区很开心地宣布，在经过4个月的版本开发之后，Flink CDC 3.4.0 版本已经正式发布。Flink CDC 是流行的流式数据集成框架，CDC 3.4.0 版本强化了框架对于高频表结构变更的支持，框架支持了 batch 执行模式&#x…...

编程日记 2025/6/27 23:10:13

NIFI的处理器:JSLTTransformJSON 2.4.0

该处理器使用JSLT转换FlowFile JSON有效负载的格式。使用转换后的内容创建新的FlowFile，并将其路由到“成功”关系。如果JSLT转换失败，则将原始FlowFile路由到“失败”关系。需要注意的是，编译JSLT转换可能相当昂贵。理想情况下&#xff0c…...

编程日记 2025/6/27 22:57:56

k8s-ServiceAccount 配置

在 Kubernetes 中 ServiceAccount 是一种为 Pod 提供身份认证的机制，允许 Pod 以特定的身份访问 Kubernetes API 服务器。 **Role（角色）**是 Kubernetes 中定义权限的资源对象，它只能在特定的命名空间内生效。Role 用于定义一组权…...

编程日记 2025/6/27 23:12:03

Python Lambda 表达式

在 Python 编程中，Lambda 表达式是一个非常强大且实用的工具，它就像一把瑞士军刀，能在各种场景下帮助我们写出简洁、优雅的代码。接下来，就让我们一起深入探索 Python Lambda 表达式的奥秘。一、Lambda 表达式的基础认知 1…...

编程日记 2025/7/4 6:00:46

【ffmpeg】ffprobe基本用法

ffprobe 是 FFmpeg 工具集中的一个强大命令行工具，主要用于分析多媒体文件（如视频、音频等）的格式和内容信息。它可以提取文件的元数据、编解码器信息、流详情、帧信息等，而无需对文件进行转码或修改。基本用法 ffprobe [选项] …...

编程日记 2025/6/27 23:31:48

Java 代码生成工具：如何快速构建项目骨架？

Java 代码生成工具：如何快速构建项目骨架？ 在 Java 项目开发过程中，构建项目骨架是一项繁琐但又基础重要的工作。幸运的是，Java 领域有许多代码生成工具可以帮助我们快速完成这一任务，大大提高开发效率。一、代码生…...

编程日记 2025/6/27 22:57:57

模板初阶【C++】

一、泛型编程前言： 我们经常会用到数据的交换，C中的函数重载可以完成 //函数重载 void swap(int& x,int& y) {int tmp x;x y;y tmp; }void swap(double& x, double& y) {double tmp x;x y;y tmp; }void swap(char& x, ch…...

编程日记 2025/6/27 23:16:33

URL 类知识点详解

URL 类知识点详解 1. 基本概念与位置所属包: java.net.URL核心功能: 表示统一资源定位符（Uniform Resource Locator），用于标识和定位网络资源（如网页、文件、API接口）。支持多种协议：HTTP、HTTPS、FTP、file（本地文件）等。不可变类：一旦创建，内容不可修改（线程安全…...

编程日记 2025/6/27 23:38:50