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

快速幂

876. 快速幂求逆元 - AcWing题库

AC代码:
 

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;typedef long long ll;int n;int qmi(int a,int k,int p)
{int res=1;while(k){if(k&1)res=(ll)res*a%p;k>>=1;a=(ll)a*a%p;}return res;
}int main()
{scanf("%d",&n);while(n--){int a,k,p;scanf("%d%d%d",&a,&k,&p);int t=qmi(a,k,p);printf("%d\n",t);}return 0;
}

相关解释:

这里如果暴力做的话,每次都会遍历k次,也就是2*10^9,一共有100000次,显然会超时,所以就需要采用快速幂来求解。

假设要求a得k次方模p的结果,只需要求出a的0次方,a的1次方,...,a的logk次方这些就可以了,将复杂度o(k)转化为o(log k)。每次对于k的最后一位看看是不是1,是1就乘上a(这里a是没k的右移而变化)。这里刚开始是第0位,所以乘上a,如果是第1位,就需要乘上a^2,第2位就需要乘上a^4,所以每次都a乘以a更新a就可以了。

还有一点,一般数论的题要开long long,并且两个数相乘的话,要在前面加个(ll)。

相关文章:

快速幂

876. 快速幂求逆元 - AcWing题库 AC代码&#xff1a; #include <iostream> #include <cstring> #include <algorithm>using namespace std;typedef long long ll;int n;int qmi(int a,int k,int p) {int res1;while(k){if(k&1)res(ll)res*a%p;k>&…...

【题解 动态规划】 Colored Rectangles

题目描述&#xff1a; 分析&#xff1a; 乍一看我还以为是贪心&#xff01; 猫 想想感觉没问题 但是局部最优并不能保证全局最优 比如这组数据 19 19 19 19 20 20 20 20如果按照贪心的做法&#xff0c;答案是20*20*2 但是其实答案是19*20*4 因此这道题用贪心是不对的 于是我…...

VsCode好用的扩展插件

开发插件推荐: 别名路径跳转 >> 点击引用的变量名&#xff0c;ctrl 点击 跳转文件Auto Rename Tag >> 修改标签前缀&#xff0c;后缀标签会同时修改Chinees 中文(简体)Code Runner >> 纯js文件右键点击run code即可底部终端打印file-icons-mac >> ma…...

Linux shell编程学习笔记4:修改命令行提示符格式(内容和颜色)

一、命令行提示符格式内容因shell类型而异 Linux终端命令行提示符内容格式则因shell的类型而异&#xff0c;例如CoreLinux默认的shell是sh&#xff0c;其命令行提示符为黑底白字&#xff0c;内容为&#xff1a; tcbox:/$ 其中&#xff0c;tc为当前用户名&#xff0c;box为主机…...

vue-引入使用main.js全局常量

common.js 命名什么都可以&#xff0c;用来定义常量的 定义了之后使用export让此暴露出去 const QRaddress http://localhost:9875export{QRaddress, } main.js //引入刚刚的js import {QRaddress} from /config/common.js挂载 Vue.prototype.$QRaddress QRaddress使用 …...

【C语言】【动态内存管理】malloc,free,calloc,realloc

1.malloc函数 void* malloc(size_t size)功能&#xff1a;向内存申请字节为 size大小的空间 使用时要包含头文件&#xff1a;<stdlib.h> 开辟成功&#xff1a;返回开辟好的空间初始地址的指针 开辟失败&#xff1a;返回空指针 NULL 使用举例&#xff1a; (malloc和free…...

Linux性能优化--性能工具-系统CPU

2.0.概述 本章概述了系统级的Linux性能工具。这些工具是你追踪性能问题时的第一道防线。它们能展示整个系统的性能情况和哪些部分表现不好。 1.理解系统级性能的基本指标&#xff0c;包括CPU的使用情况。 2.明白哪些工具可以检索这些系统级性能指标。 2.1CPU性能统计信息 为…...

Ipython和Jupyter Notebook介绍

Ipython和Jupyter Notebook介绍 Python、IPython和Jupyter Notebook是三个不同但密切相关的工具。简而言之&#xff0c;Python是编程语言本身&#xff0c;IPython是对Python的增强版本&#xff0c;而Jupyter Notebook是一种在Web上进行交互式计算的环境&#xff0c;使用IPytho…...

数列极差(c++题解)

题目描述 佳佳的老师在黑板上写了一个由 n个正整数组成的数列&#xff0c;要求佳佳进行如下操作&#xff1a;每次擦去其中的两个数a 和b &#xff0c;然后在数列中加入一个数a*b1 &#xff0c;如此下去直至黑板上剩下一个数为止&#xff0c;在所有按这种操作方式最后得到的数…...

面试题:熟悉设计模式吗?谈谈简单工厂模式和策略模式的区别

刚刚接触设计模式的时候&#xff0c;我相信单例模式和工厂模式应该是用的最多的&#xff0c;毕竟很多的底层代码几乎都用了这些模式。自从接触了一次阿里的公众号发的一次文章关于 DDD的使用 以后&#xff0c;就逐渐接触了策略模式。现在在项目中运用最多的也是这几种设计模式了…...

Windows + Git + TortoiseGit + Github

一、下载Git&#xff08;Git For Windows&#xff09; 1.1. Git下载地址&#xff1a;https://gitforwindows.org/ 1.2. 默认安装即可&#xff08;包名&#xff1a;Git-2.42.0.2-64-bit.exe&#xff09; 二、下载TortoiseGit 2.1.TortoiseGit下载地址&#xff1a;http://tortoi…...

MySQL数据库索引练习

1.学生表&#xff1a;Student (Sno, Sname, Ssex , Sage, Sdept) 学号&#xff0c;姓名&#xff0c;性别&#xff0c;年龄&#xff0c;所在系 Sno为主键 课程表&#xff1a;Course (Cno, Cname,) 课程号&#xff0c;课程名 Cno为主键 学生选课表&#xff1a;SC (Sno, Cno, Scor…...

mysql面试题10:MySQL中有哪几种锁?表级锁、行级锁、页面锁区别和联系?

该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 面试官:Mysql中有哪几种锁? 在MySQL中,主要有以下几种类型的锁: 共享锁(Shared Lock):也称为读锁。多个事务可以同时持有共享锁,可以读取但不能修…...

ctfshow—1024系列练习

1024 柏拉图 有点像rce远程执行&#xff0c;有四个按钮&#xff0c;分别对应四份php文件&#xff0c;开始搞一下。一开始&#xff0c;先要试探出 文件上传到哪里&#xff1f; 怎么读取上传的文件&#xff1f; 第一步&#xff1a;试探上传文件位置 直接用burp抓包&#xff0c;…...

javaWeb学生信息管理

一、引言 学生信息管理系统是基于Java Web技术开发的一个全栈应用&#xff0c;用于管理学生的基本信息。本系统采用Eclipse作为开发工具&#xff0c;Navicat用于MySQL数据库管理&#xff0c;运行在JDK1.8、Tomcat9.0、MySQL8.0环境下。前端采用JavaScript、jQuery、Bootstrap4…...

玩转gpgpu-sim 04记—— __cudaRegisterBinary() of gpgpu-sim 到底做了什么

官方文档&#xff1a; GPGPU-Sim 3.x Manual __cudaRegisterBinary(void*) 被执行到的代码逻辑如下&#xff1a; void** CUDARTAPI __cudaRegisterFatBinary( void *fatCubin ) { #if (CUDART_VERSION < 2010)printf("GPGPU-Sim PTX: ERROR ** this version of GPGPU…...

S-Clustr(影子集群)僵尸网络@Мартин.

公告 项目地址:https://github.com/MartinxMax/S-Clustr/tree/V1.0.0 1.成功扩展3类嵌入式设备,组建庞大的"僵尸网络" |——C51[开发中] |——Arduino |——合宙AIR780e[开发中] 2.攻击者端与服务端之间通讯过程全程加密,防溯源分析 3.Generate一键自动生成Arduino…...

认识PostgreSQL

深入认识PostgreSQL&#xff1a;开源世界的强大数据库 在当今数字化时代&#xff0c;数据是组织的最宝贵资源之一。数据库管理系统&#xff08;DBMS&#xff09;扮演着关键角色&#xff0c;帮助企业存储、管理和分析数据。PostgreSQL&#xff0c;作为一款开源的高级关系型数据库…...

基本的五大排序算法

目录&#xff1a; 一&#xff0c;直接插入算法 二&#xff0c;希尔排序算法 三&#xff0c;选择排序 四&#xff0c;堆排序 五&#xff0c;冒泡排序算法 简介&#xff1a; 排序算法目前是我们最常用的算法之一&#xff0c;据研究表明&#xff0c;目前排序占用计算机CPU的时…...

封装api的理解

1.基地址(baseUrl) (1).测试环境 用于测试环境的运行 (2).正式环境 用于正式环境的运行 2.拦截器 1.请求拦截器 (1)成功的回调 做的事情:例如在请求头header里面加入toekn。 (2)失败的回调 直接返回失败的结果: return promise.reject(error) 2.响应拦截器 (1)成功的回…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

Java 8 Stream API 入门到实践详解

一、告别 for 循环&#xff01; 传统痛点&#xff1a; Java 8 之前&#xff0c;集合操作离不开冗长的 for 循环和匿名类。例如&#xff0c;过滤列表中的偶数&#xff1a; List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

Spring数据访问模块设计

前面我们已经完成了IoC和web模块的设计&#xff0c;聪明的码友立马就知道了&#xff0c;该到数据访问模块了&#xff0c;要不就这俩玩个6啊&#xff0c;查库势在必行&#xff0c;至此&#xff0c;它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据&#xff08;数据库、No…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...