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

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

智能推荐

亚马逊云科技AWS免费证书-EC2服务器设计(含题库)

▶️ AWS Educate(免费教育计划)：它是面向在校学生、AWS初学者，帮助他们学习、精通AWS的免费项目。除了这张开发者证书，还有其他9张关于serverless无服务器开发、Web系统开发、数据库、DevOps、DeepRacer(AWS 无人驾驶服务)等多个免费证书可以拿，快跟着小李哥一起也拿下AWS 52张认证！这次证书是关于AWS EC2实例的设计和搭建，EC2作为AWS服务的核心，是学好AWS的第一步。▶️ 课程包括图中视频和实验课程(可以不看，点Next直接跳过到最后的测试)

微信小程序与web-view网页进行通信的尝试

首先，微信小程序向web-view传递数据一般通过地址栏传参的形式（给src赋值或者修改hash），这样一般就已经能够满足实际开发需求了，所以这里主要探讨web-view向微信小程序传参。

安装texstudio的坑_texstudio无法找到入口-程序员宅基地

文章浏览阅读1.2k次。最后看了一篇博客，说有可能是中间安装了winedt，在 WinEdt 内的 ctex 发行版(其实是一个 miktex 引擎)会覆盖这个环境变量, 导致 texlive 发行版找不到 tex 引擎以及对应的 fmt 文件, 引起了上述的错误。重复卸载下载多次后都无法解决问题。怀疑可能是版本不适配问题，于是在https://sourceforge.net/projects/texstudio/files/4.0.0/下载了4.0.0版本，终于成功打开texstudio了！所以尝试在环境变量处添加：【来源。_texstudio无法找到入口

学习Rust的第29天: cat in Rust

否则，假设提供了文件名，并且它将继续读取和打印这些文件的内容，当前将其作为注释保留。函数将命令行参数收集到字符串向量中，删除第一个参数（程序名称本身），然后。方法当前留空，可能会被实现来读取和打印指定文件的内容。方法读取由名称指定的文件的内容并将其作为 a 返回。它首先检查是否没有提供文件名，在这种情况下它调用。它检查是否没有提供文件名，在这种情况下它调用。文件名中是否存在该标志，如果存在，则调用该。文件名中是否存在该标志，如果存在，则调用该。否则，它会迭代每个文件名，使用读取其内容。

GitHub Copilot Workspace：欢迎进入原生Copilot开发环境

一旦你对计划感到满意，你可以直接在Copilot Workspace中运行你的代码，跳入底层的GitHub Codespace，并调整所有代码更改直到你对最终结果感到满意。在去年GitHub Universe的早期展示后，今天，我们正重新想象开发者体验的本质，推出了GitHub Copilot Workspace的技术预览版：一个原生支持Copilot的开发环境。然后剩下的就是提交你的拉取请求，运行你的GitHub Actions，进行安全代码扫描，并请求你的团队成员进行人工代码审查。而且完全可以编辑……

【微机原理复试面试简答题汇总】_微机原理复试常见问题-程序员宅基地

文章浏览阅读1.2k次，点赞6次，收藏29次。提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档。_微机原理复试常见问题

随便推点

WML(Wireless Markup Language - 无线标记语言)_无线标记语言的特点-程序员宅基地

文章浏览阅读583次。WML　　WML(Wireless Markup Language - 无线标记语言)。它是一种从 HTML 继承而来的标记语言，但是 WML 基于 XML，因此它较 HTML 更严格。　　WML 被用来创建可显示在 WAP 浏览器中的页面。用WML编写的页面被称为 DECKS。DECKS 是作为一套 CARDS 被构造的。　　这种描述语言同我们常听说的HTML语言同出一家，都属于XML语言这一大_无线标记语言的特点

23种设计模式（第三章结构型模式7种）_设计模式符合-程序员宅基地

文章浏览阅读307次。结构型模式结构型模式描述如何将类或对象按某种布局组成更大的结构。它分为类结构型模式和对象结构型模式，前者采用继承机制来组织接口和类，后者釆用组合或聚合来组合对象。由于组合关系或聚合关系比继承关系耦合度低，满足“合成复用原则”，所以对象结构型模式比类结构型模式具有更大的灵活性。结构型模式分为以下 7 种：代理模式适配器模式装饰者模式桥接模式外观模式组合模式享元模式5.1 代理模式5.1.1 概述由于某些原因需要给某对象提供一个代理以控制对该对象的访问。这时，访问对象不适合或者不能_设计模式符合

链表中为何使用二级指针_链表初始化为什么要二级指针-程序员宅基地

文章浏览阅读3.6k次，点赞30次，收藏128次。本篇目录前言参数的调用方式传值调用传址调用传引用调用示例说明使用二级指针/一级指针创建链表时的对比主函数中作此调用使用二级指针创建链表使用一级指针创建链表会成功吗销毁链表时二级指针和一级指针的对比使用二级指针销毁链表使用一级指针销毁链表会成功吗总结完整代码参考来源前言在学习数据结构时，在链表初始化或者销毁链表的时候，经常使用二级指针或者一级指针的引用，这是为什么呢？同样是指向内存单元的地址，为什么就不能使用一级指针呢？使用一级指针去初始化或者是销毁链表的时候，究竟会发生什么呢？到底什么时候该用二级指针，_链表初始化为什么要二级指针