【代码超详解 · 附参考模板】洛谷 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;
}

本文链接：https://blog.csdn.net/COFACTOR/article/details/103158950

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

“码农”一词是怎么来的？为什么中国程序员会被码农？程序员和农民有什么关联？-程序员宅基地

文章浏览阅读1.7w次。原创：思齐大神来源：蚁开源社区很多同学会问，IT行业在中国并不是特别差的行业，而程序员的工资也并不低，但为什么中国的程序员总被称作码农或者说是苦逼的程序员？中国的程序员生活和欧美的有什么不一样？先说两个小段子街边，一对情侣在吵架。女孩对男孩说，“我们分手吧！”男孩沉默半天，开口问道，“我能再说最后一句话吗？”“说吧，婆婆妈妈的。”“我会编程……”“会编程有个屁用啊，现在到处都是会编程的人！”男孩涨红了脸，接着说道，“我会编程……我会变成…童话里，你爱的那个天使……”【程序._码农

Java初学者也能看的懂的AQS_aqs对接-程序员宅基地

文章浏览阅读259次。Java初学者也能看的懂的AQS学习AQS之前，你需要了解以下内容，如果不是很清楚，那么理解本文会有点吃力。（Java初学者得会一下内容）synchronizedCASLock前言synchronized首先我们知道synchronized是Java关键字，上锁释放锁等一切操作都是由JVM控制的。我们只能通过虚拟机的C++才能去研究其底层实现。我们除了判断synchronized是作为方法的修饰符，还是当做同步代码块使用以外，没什么需要我们程序员操作的。cas一种自旋的原子操作，也是J_aqs对接

【JZOJ5262】【GDOI2018模拟8.12】树(DP，性质题)_gdoi2018省选模拟树-程序员宅基地

文章浏览阅读460次。DescriptionSolution首先我们可以知道两个性质：1、路径u-v和路径v-w可以合并为路径u-w；2、路径u1-v1加路径u2-v2和路径u1-v2加路径u2-v1是等价的(就是起始点和终点可以互换) 那么知道这些性质之后就很好做了。我们只用知道每个点多少次做起点和多少次做终点。我们设f[i]表示满足i子树的需求i上的值要是多少。那么枚举i的所有儿子，判断a[i]-f[i]，_gdoi2018省选模拟树

[PTA]7-65 字符串替换 (15 分)含思路_字符串替换pta-程序员宅基地

文章浏览阅读2.8k次，点赞4次，收藏28次。我们进行简单的运算即可实现倒序。_字符串替换pta

linux网络设置_linux如何开启网络连接-程序员宅基地

文章浏览阅读4k次，点赞5次，收藏22次。traceroute 180.101.50.188————————测试到180.101.50.188有多少个网关。vim /etc/sysconfig/static-routes——————————修改。netstat -antp | grep 22———————查看端口号22的相关信息。systemctl restart network————————————重启。systemctl restart network————————重新启动。_linux如何开启网络连接

pr中，视频导入后，视频画面大小显示不完整应该如何解决？_avi视频到pr里会放大-程序员宅基地

文章浏览阅读4w次，点赞23次，收藏6次。本人pr小白，今天编辑视频时候遇到了问题，也解决了，所以分享记录一下。问题一视频下面原来有字幕的，可是导入的视频变大了，现在看不到了怎么办？还有就是，频导入之后画质好像变糊了又是为什么？解决：将箭头放到要编辑的视频那里，右击，然后点击设为帧大小这样完整的视频就出来了。问题二如果视频模糊，就是序列设置的不对要先新建序列一般的都是1920×1080本人博客：https://blog.csdn.net/weixin_46654114本人b站求关注：https://space.bi_avi视频到pr里会放大

随便推点

SeetaFace2 Android 平台编译_seetafacerecognizer2.0.ats-程序员宅基地

文章浏览阅读4.1k次。SeetaFace2 Android 平台编译项目地址：https://github.com/seetafaceengine/SeetaFace2SeetaFace2 人脸识别引擎包括了搭建一套全自动人脸识别系统所需的三个核心模块，即：人脸检测模块 FaceDetector、面部关键点定位模块 FaceLandmarker 以及人脸特征提取与比对模块 FaceRecognizer。面部关键点定位支持 5 点和 81 点定位，两个辅助模块 FaceTracker 和 QualityAssessor 用_seetafacerecognizer2.0.ats

Oracle删除约束和主键的语句_oracle删除主键的sql语句-程序员宅基地

文章浏览阅读3.2w次，点赞4次，收藏34次。1.删除约束语句：alter table 表名 drop constraint 约束名；alter table mz_sf4 drop constraint pk_id1;2.删除主键语句：alter table 表名 drop primary key;alter table mz_sf3 drop primary key;如果出错：ORA-02273：此唯一主键已_oracle删除主键的sql语句

MySQL~InnoDB的备份和主从复制-程序员宅基地

文章浏览阅读989次，点赞9次，收藏13次。这份面试题几乎包含了他在一年内遇到的所有面试题以及答案，甚至包括面试中的细节对话以及语录，可谓是细节到极致，甚至简历优化和怎么投简历更容易得到面试机会也包括在内！也包括教你怎么去获得一些大厂，比如阿里，腾讯的内推名额！某位名人说过成功是靠99%的汗水和1%的机遇得到的，而你想获得那1%的机遇你首先就得付出99%的汗水！你只有朝着你的目标一步一步坚持不懈的走下去你才能有机会获得成功！成功只会留给那些有准备的人！《一线大厂Java面试题解析+核心总结学习笔记+最新讲解视频+实战项目源码》点击传送门即可获取。