null - 程序员宅基地

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

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

智能推荐

vue引入原生高德地图_前端引入原生地图-程序员宅基地

文章浏览阅读556次，点赞2次，收藏3次。由于工作上的需要，今天捣鼓了半天高德地图。如果定制化开发需求不太高的话，可以用vue-amap，这个我就不多说了，详细就看官网 https://elemefe.github.io/vue-amap/#/zh-cn/introduction/install然而我们公司需要英文版的高德，我看vue-amap中好像没有这方面的配置，而且还有一些其他的定制化开发需求，然后就只用原生的高德。其实原生的引入也不复杂，但是有几个坑要填一下。1. index.html注意，引入的高德js一定要放在头部而_前端引入原生地图

ViewGroup重写大法（一）-程序员宅基地

文章浏览阅读104次。本文介绍ViewGroup重写，我们所熟知的LinearLayout，RelativeLayout，FrameLayout等等，所有的容器类都是ViewGroup的子类，ViewGroup又继承View。我们在熟练应用这些现成的系统布局的时候可能有时候就不能满足我们自己的需求了，这是我们就要自己重写一个容器来实现效果。ViewGroup重写可以达到各种效果，下面写一个简单的重写一个Vi..._viewgroup 重写

Stm32学习笔记，3万字超详细_stm32笔记-程序员宅基地

文章浏览阅读1.8w次，点赞279次，收藏1.5k次。本文章主要记录本人在学习stm32过程中的笔记，也插入了不少的例程代码，方便到时候CV。绝大多数内容为本人手写，小部分来自stm32官方的中文参考手册以及网上其他文章；代码部分大多来自江科大和正点原子的例程，注释是我自己添加；配图来自江科大/正点原子/中文参考手册。笔记内容都是平时自己一点点添加，不知不觉都已经这么长了。其实每一个标题其实都可以发一篇，但是这样搞太琐碎了，所以还是就这样吧。_stm32笔记

CTS(13)---CTS 测试之Media相关测试failed 小结（一）_mediacodec框架 cts-程序员宅基地

文章浏览阅读1.8k次。Android o CTS 测试之Media相关测试failed 小结（一）CTSCTS 即兼容性测试套件，CTS 在桌面设备上运行，并直接在连接的设备或模拟器上执行测试用例。CTS 是一套单元测试，旨在集成到工程师构建设备的日常工作流程（例如通过连续构建系统）中。其目的是尽早发现不兼容性，并确保软件在整个开发过程中保持兼容性。CTS 是一个自动化测试工具，其中包括两个主要软件组件：CTS tra..._mediacodec框架 cts

chosen.js插件使用，回显，动态添加选项-程序员宅基地

文章浏览阅读4.5k次。官网：https://harvesthq.github.io/chosen/实例化$(".chosen-select").chosen({disable_search_threshold: 10});赋值var optValue = $(".chosen-select").val();回显1.设置回显的值$(".chosen-select").val(“opt1”);2.触发cho..._chosen.js

C++ uint8_t数据串如何按位写入_unit8_t 集合赋值 c++-程序员宅基地

文章浏览阅读1.9k次。撸码不易，网上找不到，索性自己写，且撸且珍惜！void bitsWrite(uint8_t* buff, int pos, int size, uint32_t value){ uint32_t index[] = { 0x80000000, 0x40000000, 0x20000000, 0x10000000, 0x8000000, 0x4000000, 0x2000000, 0x1000000, 0x800000, 0x400000, 0_unit8_t 集合赋值 c++

随便推点

Javaweb框架思维导图_javaweb框架图-程序员宅基地

文章浏览阅读748次。javaweb知识点_javaweb框架图

adb的升级与版本更新_adb iptabls怎么升级-程序员宅基地

文章浏览阅读1.1w次，点赞3次，收藏16次。adb是没有自动升级的命令的，如果想要更新adb的版本，我们可以在网上找到自己想要的版本进行更新给大家提供几个版本https://pan.baidu.com/s/1yd0dsmWn5CK08MlyuubR7g&shfl=shareset 提取码: 94z81、下载解压后我们可以找到下面几个文件，并复制2、找到adb安装的文件夹下的platform-tools文件夹，我这里是..._adb iptabls怎么升级

微信苹果版删除所有的聊天记录的图文教程_mac微信怎么删除聊天列表-程序员宅基地

文章浏览阅读3.8k次。很多用户可能都知道怎么在Windows系统上删除微信的聊天记录，那么苹果电脑上的微信软件怎么删除所有的聊天记录呢？下面小编就专门来给大家讲下微信mac版删除所有的聊天记录的图文教程。点击后会弹出提示窗口，点击这里的确认按钮就可以将其清理掉了。在这里选择要清理的数据，然后点击下方右边的清理按钮就行了。在mac上打开微信后，点击左下角的横线图标。然后再点击这里的管理微信聊天数据按钮。打开了设置窗口，点击上方的“通用”。在这里点击下方的前往清理按钮。点击弹出菜单里的“设置”。_mac微信怎么删除聊天列表

【报错笔记】数据类型转换时报错：Request processing failed；nested exception is java.lang.NumberFormatException:..._request processing failed; nested exception is jav-程序员宅基地

文章浏览阅读7.7k次。数据类型转换时报错：Request processing failed;nested exception is java.lang.NumberFormatException:For input String “20151512345”报错原因：数字格式异常，接着后面有 For input string: “201515612343” 提示，这就告诉我们你当前想把 “201515612343” 转换成数字类型时出错了。解决方案：使用2015151612343这个数字太大了，所以直接使用string_request processing failed; nested exception is java.lang.numberformatexcepti

qml 自定义消息框_Qt qml 自定义消息提示框-程序员宅基地

文章浏览阅读387次。版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。本文链接：https://blog.csdn.net/a844651990/article/details/78376767Qt qml 自定义消息提示框QtQuick有提供比较传统的信息提示框MessageDialog，但是实际开发过程并不太能满足我们的需求。下面是根据controls2模块中..._qml 自定义 messagedialog

Redis.conf 默认出厂内容_默认出厂的原始redis.conf文件全部内容-程序员宅基地

文章浏览阅读599次。# Redis configuration file example.## Note that in order to read the configuration file, Redis must be# started with the file path as first argument:## ./redis-server /path/to/redis.conf # Note on units: when memory size is needed, it is pos._默认出厂的原始redis.conf文件全部内容