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

【算法基础 数学】快速幂

题目描述

给定 n n n a i , b i , p i a_i,b_i,p_i ai,bi,pi,对于每组数据,求出 a i b i m o d p i a_i^{b^i}~mod~p_i aibi mod pi 的值。

样例

输入样例:

2
3 2 5
4 3 9

输出样例:

4
1

快速幂解决的问题

用来解决快速的求解 a k m o d a^k~mod ak mod p p p的结果
时间复杂度为 O ( l o g k ) O(logk) O(logk)

原理(反复平方法)

预处理出来这些值:
a 2 0 m o d p a^{2^0}~mod~p a20 mod p
a 2 1 m o d p a^{2^1}~mod~p a21 mod p
a 2 2 m o d p a^{2^2}~mod~p a22 mod p
. . . ... ...
a 2 l o g k m o d p a^{2^{logk}}~mod~p a2logk mod p

大概是logk个

a k a^k ak可以表示为前面分解的这些数的某些数的乘积
k k k可以表示为 2 2 2的若干次幂的和
(利用k的二进制表示)
a k = a 2 x 1 a 2 x 2 . . . a 2 x t = a 2 x 1 + 2 x 2 + . . . + 2 x t a^k =a^{2^{x_1}}a^{2^{x_2}}...a^{2^{x_t}} =a^{2^{x_1}+2^{x_2}+...+2^{x_t}} ak=a2x1a2x2...a2xt=a2x1+2x2+...+2xt

如何求 a x a^x ax
a 1 = a a^1~=~a a1 = a
a 2 1 = ( a 1 ) 2 a^{2^1}~=~(a^{1})^2 a21 = (a1)2
a 2 2 = ( a 2 1 ) 2 a^{2^2}~=~(a^{2^1})^2 a22 = (a21)2
. . . ... ...
a 2 l o g k = ( a 2 l o g k − 1 ) 2 a^{2^{logk}}~=~(a^{2^{logk}-1})^2 a2logk = (a2logk1)2

也就是说,后一个数都是前一个数的平方
也就是经过k次迭代,就可以把这些数分解出来了
其实就是看k的二进制表示里面,哪些位是1,把1对应的这些位对应的数乘起来就可以了


代码
#include<iostream>
#include<algorithm>
using namespace std;typedef long long LL;LL qmi(int a, int k, int p){LL res = 1 % p;while(k){if(k & 1) res = res * a % p;    //如果最后一位是1,乘上a^2^a%pa = a * (LL)a % p;  //a向后迭代,继续平方k >>= 1;    //把k的最后以为删掉}return res;
}int main(){int n, a, b, p;cin >> n;while(n--){scanf("%d%d%d", &a, &b, &p);printf("%lld\n", qmi(a, b, p));}return 0;
}

作者:为梦而生
链接:https://www.acwing.com/solution/content/220897/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

相关文章:

【算法基础 数学】快速幂

题目描述 给定 n n n组 a i , b i , p i a_i,b_i,p_i ai​,bi​,pi​&#xff0c;对于每组数据&#xff0c;求出 a i b i m o d p i a_i^{b^i}~mod~p_i aibi​ mod pi​ 的值。 样例 输入样例&#xff1a; 2 3 2 5 4 3 9输出样例&#xff1a; 4 1快速幂解决的问题 用来…...

2024年华为OD机考高分攻略-完整题库-两周350分

华为OD是个不错的机会&#xff0c;很适合非软件行业到软件行业的转身。 但是很多同学之前没有软件基础&#xff0c;不知道该如何高效的准备OD机考。 我是一名软件培训老师&#xff0c;我的学生有上百人顺利通过了华为OD机考&#xff0c;并取得了高分&#xff0c;我将经验分享…...

【微信小程序独立开发 4】基本信息编辑

这一节完成基本信息的编辑和保存 首先完成用户头像的获取 头像选择 需要将 button 组件 open-type 的值设置为 chooseAvatar&#xff0c;当用户选择需要使用的头像之后&#xff0c;可以通过 bindchooseavatar 事件回调获取到头像信息的临时路径。 从基础库2.24.4版本起&…...

Docker-基础指令

前置知识 docker官网地址&#xff1a;https://www.docker.com/ docker镜像地址&#xff1a;https://hub.docker.com/ docker安装教程&#xff1a;https://docs.docker.com/engine/install/centos/ 安装只需要注意将仓库源改为国内就好,推荐去阿里云注册自己的账号获得加速地址…...

JUC-Java内存模型JMM

JMM概述 Java Meory Model java内存模型。在不同的硬件和不同的操作系统上&#xff0c;对内存的访问方式是不一样的。这就造成了同一套java代码运行在不同的操作系统上会出问题。JMM就屏蔽掉硬件和操作系统的差异&#xff0c;增加java代码的可移植性。这是一方面。 另一方面JM…...

uni-app使用HBuilderX打包Web项目

非常简单&#xff0c;就是容易忘记 一、找到manifest.json配置Web配置 二、源码视图配置 "h5" : {"template" : "","domain" : "xxx.xx.xx.xxx","publicPath" : "./","devServer" : {&quo…...

前后置、断言、提取变量、数据库操作功能

前置操作和后置操作都是 API 请求在发送和响应过程中执行的脚本&#xff0c;主要用于在发起 API 请求前和获得响应后完成验证或执行某些操作&#xff0c;目的是为了提高 API 调试和测试的效率&#xff0c;并确保接口的正确性。 前置操作​ 前置操作是在 API 请求之前执行的脚本…...

三子棋/井字棋(C语言)

这个游戏需要用到三个文件 game.h头文件用来申明函数和导包 game.h如下: #pragma once #define ROW 3 #define COL 3 #include <stdlib.h> #include <time.h> #include <stdio.h>//初始化棋盘的函数void InitBoard(char board[ROW][COL], int row, int co…...

数据结构小项目----通讯录的实现(这里用链表实现) 超详细~~~~૮(˶ᵔ ᵕ ᵔ˶)ა

目录 Contact.h说明&#xff1a; 结构体与头文件的包含&#xff1a; ​编辑 函数在头文件的声明与定义&#xff1a; Contact.c中各个函数的实现&#xff1a; 1.检查链表中的数据是否满了&#xff0c;满了就扩容 2.链表的尾插 3.链表的删除 4.查找名字是否匹配 5.初始化通讯…...

Electron Apple SignIn 登录

本人写博客&#xff0c;向来主张&#xff1a;代码要完整&#xff0c;代码可运行&#xff0c;文中不留下任何疑惑。 最讨厌写博客&#xff0c;代码只留下片段&#xff0c;文中关键的东西没写清楚。之前看了那么多文章&#xff0c;就是不告诉我clientId从哪来的。 官方资料地址&…...

常用中间件漏洞

IIS6 IIS7 安装 控制面板-----打开关闭windows功能 添加角色-----添加IIS 启动之后访问localhost 复现 服务器换成IIS7 访问报错 大概就是缺少CGI模块 问题解决 添加php-cgi的路径 添加脚本映射 修改php.ini文件 将 cgi.fix_pathinfo1 然后设置一个图片 访问 在后缀加上/.…...

Windows系统使用手册

点击前往查看&#x1f517;我的博客文章目录 Windows系统使用手册 文章目录 Windows系统使用手册Windows10解决大小核调度问题Windows系统安装软件Windows系统Typora快捷键Windows系统压缩包方式安装redisWindows安装dockerWindows系统的docker设置阿里源Windows系统下使用doc…...

mp4文件可以转成mp3音频吗

现在是个非常流行刷短视频一个年代&#xff0c;刷短视似乎成了人们休闲娱乐的一种方式&#xff0c;在日常刷短视频过程中&#xff0c;肯定会有很多同学被短视频 bgm 神曲洗脑&#xff0c;比如很多被网红翻唱带火的歌曲&#xff0c;例如其中"不负人间”&#xff0c;就是其中…...

Java-IO流【登录注册小项目】

♥️作者&#xff1a;白日参商 &#x1f935;‍♂️个人主页&#xff1a;白日参商主页 ♥️坚持分析平时学习到的项目以及学习到的软件开发知识&#xff0c;和大家一起努力呀&#xff01;&#xff01;&#xff01; &#x1f388;&#x1f388;加油&#xff01; 加油&#xff01…...

数字化金融时代:探讨全球金融科技创新的最新动态

在当今数字化金融时代&#xff0c;金融科技创新如影随形&#xff0c;迅猛发展。本文将深入探讨全球范围内金融科技的最新动态&#xff0c;剖析各地新兴趋势与突破。从区块链技术的应用到人工智能在金融领域的崭露头角&#xff0c;我们将一一解读这个正在不断演变的金融科技画卷…...

LeetCode:206. 反转链表

力扣链接 算法思想&#xff1a;由于单链表是单向的&#xff0c;想要对当前元素进行操作&#xff0c;需找到前一个元素。本题利用双指针&#xff0c;初始pre指针指向NULL&#xff0c;cur指针指向head.再对局部翻转之前&#xff0c;先把下一个结点存到temp指针中。当进行完如下代…...

linux 安装nginx

介绍 官网 https://nginx.org/en/download.html 在安装nginx前首先要确认系统中安装了gcc、pcre-devel、zlib-devel、openssl-devel linux 检查是否安装过某软件包 yum -y install gcc pcre-devel zlib-devel openssl openssl-devel #下载 wget https://nginx.org/downloa…...

1.C语言——基础知识

C语言基础知识 1.第一个C语言程序2.注释3.标识符4.关键字5.数据类型6.变量7.常量8.运算符9.输入输出输入输出 1.第一个C语言程序 C语言的编程框架 #include <stdio.h> int main() {/* 我的第一个 C 程序 */printf("Hello, World! \n");return 0; }2.注释 单行…...

Redis 存在线程安全问题吗?为什么?

一个工作了 5 年的粉丝私信我。 他说自己准备了半年时间&#xff0c;想如蚂蚁金服&#xff0c;结果第一面就挂了&#xff0c;非常难过。 问题是&#xff1a; “Redis 存在线程安全问题吗&#xff1f;” 一、问题解析 关于这个问题&#xff0c;我从两个方面来回答。 第一个&a…...

无人机测绘助力实现高效、安全的城市规划

随着城市化进程的不断加快&#xff0c;城市规划显得尤为重要。而无人机测绘技术作为一种创新的工具&#xff0c;为城市规划提供了更加高效、安全的解决方案。它通过快速、精确的数据采集和分析&#xff0c;为行业提供有力的决策支持&#xff0c;助力城市规划的现代化和可持续发…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

Docker 本地安装 mysql 数据库

Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker &#xff1b;并安装。 基础操作不再赘述。 打开 macOS 终端&#xff0c;开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

现有的 Redis 分布式锁库(如 Redisson)提供了哪些便利?

现有的 Redis 分布式锁库&#xff08;如 Redisson&#xff09;相比于开发者自己基于 Redis 命令&#xff08;如 SETNX, EXPIRE, DEL&#xff09;手动实现分布式锁&#xff0c;提供了巨大的便利性和健壮性。主要体现在以下几个方面&#xff1a; 原子性保证 (Atomicity)&#xff…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...