【代码超详解 · 附参考模板】洛谷 P1226 【模板】快速幂||取余运算_洛谷批改代码系统如何实现-程序员宅基地
一、题目描述
二、算法分析说明与代码编写指导
时间复杂度：O(logn)
将上面的算法直接转换成代码是这样的：
template<typename _Ty> inline _Ty PowerMod(_Ty radix, _Ty exp, const _Ty& mod) {
_Ty ans = 1; radix %= mod;
while (exp) {
if (exp & 1)ans = (ans * radix) % mod;
exp >>= 1, radix = (radix * radix) % mod;
}return ans % mod;
}
但是这样的代码存在两个问题：一是中间变量溢出（radix * radix 时），二是时间复杂度在某些题目中可能仍然偏高（__int128类型的运算肯定比64位的整数慢）。所以我们一般采用改进版本的快速幂取模。具体代码见第四部分。
三、AC 代码
#include<cstdio>
#include<algorithm>
#pragma warning(disable:4996)
template<typename _RTy, typename _Ty1, typename _Ty2, typename _Ty3> inline _RTy PowerMod(const _Ty1& radix, const _Ty2& exp, const _Ty3& mod) {
__int128 ans = 1, R = radix, X = exp, M = mod;
R %= M;
while (X) {
if (X & 1)ans = (ans * R) % M;
X >>= 1, R = (R * R) % M;
}return ans % M;
}
int main() {
int b, p, k;
scanf("%d%d%d", &b, &p, &k);
printf("%d^%d mod %d=%d\n", b, p, k, PowerMod<int>(b, p, k));
//system("pause");
return 0;
}
四、快速幂取模算法的参考模板
强制转换中间结果为__int128类型的版本（VS下不可用）：
template<typename _RTy, typename _Ty1, typename _Ty2, typename _Ty3> inline _RTy PowerMod(const _Ty1& radix, const _Ty2& exp, const _Ty3& mod) {
__int128 ans = 1, R = radix % mod, X = exp, M = mod;
while (X) {
if (X & 1)ans = (ans * R) % M;
X >>= 1, R = (R * R) % M;
}return ans % M;
}
防止基数溢出版本（需要配合采用long double类型的快速积取模）：
template<typename _Ty> inline _Ty MultiModL(const _Ty& a, const _Ty& b, const _Ty& mod) {
return (a * b - (_Ty)((long double)a / mod * b) * mod + mod) % mod;
}
template<typename _Ty> inline _Ty PowerMod(_Ty radix, _Ty exp, const _Ty& mod) {
_Ty ans = 1; radix %= mod;
while (exp) {
if (exp & 1)ans = MultiModL(ans, radix, mod);
exp >>= 1, radix = MultiModL(radix, radix, mod);
}return ans % mod;
}
防止基数溢出版本（需要配合采用__int128类型的快速积取模，VS下不可用）：
template<typename _RTy, typename _Ty1, typename _Ty2, typename _Ty3> inline _RTy MultiMod(const _Ty1& x, const _Ty2& y, const _Ty3& m) {
return (__int128)x * y % m;
}
template<typename _Ty> inline _Ty PowerMod(_Ty radix, _Ty exp, const _Ty& mod) {
_Ty ans = 1; radix %= mod;
while (exp) {
if (exp & 1)ans = MultiMod<_Ty>(ans, radix, mod);
exp >>= 1, radix = MultiMod<_Ty>(radix, radix, mod);
}return ans % mod;
}
智能推荐
TensorFlow安装过程问题汇总_loading channels: failed-程序员宅基地
文章浏览阅读1.6k次。1. 问题： conda search numpy 以及 conda search --full-name python 失败。失败的现象：Loading channels: failedCondaHTTPError: HTTP 404 NOT FOUND for url <http://pypi.douban.com/simple/noarch/repodata.json>..._loading channels: failed
pip install sklearn安装成功后，提示ModuleNotFoundError: No module named ‘sklearn‘错误解决办法_pip sklearn库安装成功但是报错-程序员宅基地
文章浏览阅读6.5k次，点赞10次，收藏16次。pip install sklearn安装成功后，提示ModuleNotFoundError: No module named 'sklearn'错误解决办法_pip sklearn库安装成功但是报错
玩转传感器——DHT11温湿度传感器（STM32版）_温湿度传感器接线图-程序员宅基地
文章浏览阅读7.4w次，点赞327次，收藏2.3k次。玩转传感器——DHT11温湿度传感器（STM32版）文章目录玩转传感器——DHT11温湿度传感器（STM32版）前言一、接口说明1 接线图2 电源引脚3 串行接口（单线双向）二、通信过程三、测量分辨率与电气特性四、使用注意事项1 工作与贮存条件2 暴露在化学物质中3 恢复处理4 温度影响5 光线6 配线注意事项五、DHT11驱动程序1 DHT11.c1.1 配置输入输出GPIO1.2 复位DHT111.3 检查DHT11是否正常1.4 DHT11初始化1.5 读取一位数据（返回值0/1）1.6 读取一个_温湿度传感器接线图
如何把自己的驱动编译进内核或模块（Kconfig和Makefile）_nvp6324 驱动-程序员宅基地
文章浏览阅读905次。本说明以NVP6324为例。1、首先在drivers\media\i2c中修改Kconfig和Makefile，如下： 在Kconfig中添加如下：config VIDEO_NVP6324 tristate "NVP6324 AHD sensor support" depends on I2C ---help--- This is a V4L2 sensor-le..._nvp6324 驱动
自适应直方图均衡（CLAHE) 代码及详细注释【OpenCV】_自适应双平台直方图均衡算法代码-程序员宅基地
文章浏览阅读2.7w次，点赞9次，收藏80次。理论请参考博客OpenCV源码的本地路径： %OPENCV%\opencv\sources\modules\imgproc\src\clahe.cppclahe.cpp// ----------------------------------------------------------------------// CLAHEnamespace{ class C_自适应双平台直方图均衡算法代码
计算机视觉及其图像处理操作-程序员宅基地
文章浏览阅读3.1k次，点赞3次，收藏22次。点击上方“小白学视觉”，选择加"星标"或“置顶”重磅干货，第一时间送达作者丨吃猫的鱼python @CSDN编辑丨3D视觉开发者社区目录content一、什么是计算机视觉二、图片处理基础操作图片处理：读入图像图片处理：显示图像图片处理：图像保存三、图像处理入门基础图像成像原理介绍图像分类四、像素处理操作读取像素修改像素使用python中的numpy修改像素点五、获取图像属性形状像素数目图像类型六..._计算机视觉与图像处理
随便推点
JavaScript——leetcode剑指 Offer 36. 二叉搜索树与双向链表_leetcode 链表的head是什么js-程序员宅基地
文章浏览阅读157次。题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。为了让您更好地理解问题，以下面的二叉搜索树为例：我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需_leetcode 链表的head是什么js
一篇文章让你全面了解TDengine-程序员宅基地
文章浏览阅读1.5w次，点赞3次，收藏46次。一篇文章让你全面了解TDengine本文将从以下几个方面全面介绍TDengine。TDengine的基本介绍TDengine的发展历程TDengine的优势TDengine的适用场景TDengine的写入存储策略TDengine的特点TDengine的基本介绍一句话了解TDengineTDengine是一个高效的存储、查询、分析时序大数据的平台，专为物联网、车联网、工业互联网、运维监测等优化而设计。你可以像使用关系型数据库MySQL一样来使用它，简单又方便。为什么会有TDengin_tdengine
成为JavaGC专家Part II：如何监控Java垃圾回收机制-程序员宅基地
文章浏览阅读215次。 成为JavaGC专家Part II ：如何监控Java垃圾回收机制 本文是成为Java GC专家系列文章的第二篇。在第一篇《深入浅出Java垃圾回收机制》中我们学习了不同GC算法的执行过程，GC是如何工作的，什么是新生代和老年代，你应该了解的JDK7中的5种GC类型，以及这5种类型对于应用性能的影响。 在本文中，我将解释JVM到底是如何执行垃圾回收处理..._成为javagc专家part ii — 如何监控java垃圾回收机制。
python学习导航线_python点线导航-程序员宅基地
文章浏览阅读122次。文章目录python学习导航线一、seleniumpython-selenium二、python基础知识python的聊天室python学习导航线一、seleniumpython-selenium二、python基础知识python的聊天室_python点线导航
静态成员-静态成员变量-程序员宅基地
文章浏览阅读3.4k次，点赞4次，收藏22次。静态成员静态成员都是用static修饰，它的特点是不论创建多少个对象，程序都只创建一个静态成员。最主要的特点：共享什么是共享呢？例如：统计超市中所有商品数量的总和，商品数量的总和是随着每一个数量的变化而变化的，这是我们就可以用静态成员处理。（代码下面有写）静态成员又分为静态成员变量和静态成员函数。（一）静态成员变量特点：1、所有对象共享一份数据。 2、在编译阶段分配内存。 3、类内声明，类外初始化。#include<io..._静态成员变量
HTML5七夕情人节表白网页制作【情人节满屏爱心HTML5特效】HTML+CSS+JavaScript html生日快乐祝福网页制作_html 满屏爱心-程序员宅基地
文章浏览阅读879次，点赞21次，收藏20次。1 网页简介：基于HTML+CSS+JavaScript 制作七夕情人节表白网页、生日祝福、七夕告白、 求婚、浪漫爱情3D相册、炫酷代码,快来制作一款高端的表白网页送(他/她)浪漫的告白,制作修改简单,可自行更换背景音乐,文字和图片即可使用等任意html编辑软件进行运行及修改编辑等操作）。_html 满屏爱心