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

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

智能推荐

[渝粤教育] 南京邮电大学市场调查与研究参考资料_南京邮电大学市场调查与研究慕课答案-程序员宅基地

文章浏览阅读3.1k次。教育-市场调查与研究-章节资料考试资料-南京邮电大学【】第一周测验1、【单选题】市场调研帮助企业获取决策A、背景B、结果C、信息D、路径参考资料【】2、【单选题】卡夫公司向市场推出了一款新的产品，可是产品的市场表现远低于预期。卡夫公司通过市场调查来了解原因。请问下述发现不属于信息的是？A、超过一半的被访者说不知道该产品是卡夫公司出品的B、那些知道这个产品却没有购买的人说，这个产品不好吃C、该产品在面世后仅仅获得2.5%的市场份额，远低于预期的5%D、试用过后，_南京邮电大学市场调查与研究慕课答案

C3P0连接池配置文档_c3p0文档-程序员宅基地

文章浏览阅读3.4k次，点赞2次，收藏7次。一、导入jar包下载链接二、配置文件配置文件名称：c3p0-config.xml (固定)配置文件路径：src (类路径)配置文件内容：命名配置<c3p0-config>  <named-config name="test"> <!-- 连接数据库的4项基本参数 -..._c3p0文档

prim 堆优化_prim板子堆优化vector-程序员宅基地

文章浏览阅读358次。#include #include #include #include #include #include #include using namespace std;const int MAXN = 1005;const int INF = 1 << 30;struct Node { int u, w; friend bool operator<(const Node& _prim板子堆优化vector

【CODE[VS]】1023--GPA计算_gpa输入的第一行-程序员宅基地

文章浏览阅读172次。题目描述 Description        小松终于步入了大学的殿堂，带着兴奋和憧憬，他参加了信息科学技术学院的新生大会。会上，院长梅教授给大家介绍了在大学中的成绩计算方式：        需要解释一下的是，小_gpa输入的第一行

【每天1分钟】MarkDown语法学习之插入代码块_idea markdown 插入代码块-程序员宅基地

文章浏览阅读2w次，点赞8次，收藏7次。【每天1分钟】MarkDown语法学习之插入代码块Markdown在IT圈子里面比较流行的一个重要原因是，它能够轻松漂亮地插入代码。方法是，使用反引号`进行包裹即可。如果是行内代码引用，使用单个反引号进行包裹这是一段 var x = 3 行内代码如果插入一整段代码，需要至少使用两个以上反引号进行包裹，看效果：fun (x: Int, y: Int): Int { return x ..._idea markdown 插入代码块

Redis面试篇-程序员宅基地

文章浏览阅读1.3k次，点赞29次，收藏20次。缓存穿透：查询一个不存在的数据，mysql查询不到数据也不会直接写入缓存，就会导致每次请求都会去查数据库，数据库的压力增大。缓存击穿：给某一个key设置了过期时间，当key过期的时候，恰好这时间点对这个key有大量的并发请求过来，这些并发的请求可能会瞬间把DB压垮。缓存雪崩是指在同一时段大量的缓存key同时失效或者Redis服务宕机，导致大量请求到达数据库，带来巨大压力。客户端对数据库中的数据主要有两类操作，读(select)与写(DML)。缓存由于其高并发和高性能的特性，已经在项目中被广泛使用。

随便推点

算法中的各种距离（欧式距离，马氏距离，闵可夫斯基距离......）_马氏距离中间那个矩阵是啥-程序员宅基地

文章浏览阅读1.9w次，点赞7次，收藏60次。在做分类时常常需要估算不同样本之间的相似性度量(SimilarityMeasurement)，这时通常采用的方法就是计算样本间的“距离”(Distance)。采用什么样的方法计算距离是很讲究，甚至关系到分类的正确与否。　　本文的目的就是对常用的相似性度量作一个总结。本文目录：1.欧氏距离2.曼哈顿距离3. 切比雪夫距离4. 闵可夫斯基距离_马氏距离中间那个矩阵是啥

kettle 提交数据量_kettle——入门操作(表输出)详细-程序员宅基地

文章浏览阅读820次。表输出控件如下1)步骤名称，2)数据库连接，前面有过部分解释3)目标模式，数据库中的概念，引用：https://www.cnblogs.com/csniper/p/5509620.html(感谢)4)目标表：数据库中的表，这里有两种方式：(1) 应用数据库中已经存在的表，浏览表选中对应表即可，下图有部分sql功能。ddl可以执行ddl语句。(2) 创建新的表，填写表的名字，点击下面的sql就可以执..._kettle 步骤提交

Sublime 多行编辑快捷键_submlite 同时操作多行 macos-程序员宅基地

文章浏览阅读4.4k次，点赞2次，收藏2次。鼠标选中多行，按下 widows 下 Ctrl Shift L( Mac下 Command Shift L)即可同时编辑这些行；鼠标选中文本，反复按widows 下CTRL D(Mac下 Command D)即可继续向下同时选中下一个相同的文本进行同时编辑；鼠标选中文本，按下Alt F3(Win)或Ctrl Command G(Mac)即可一次性选择全部的相同文本进行同时编辑；..._submlite 同时操作多行 macos

如何双启动Linux和Windows-程序员宅基地

文章浏览阅读252次。尽管Linux是具有广泛硬件和软件支持的出色操作系统，但现实是有时您必须使用Windows，这可能是由于关键应用程序无法在Linux下运行。幸运的是，双重引导Windows和Linux非常简单-本文将向您展示如何使用Windows 10和Ubuntu 18.04进行设置。在开始之前，请确保已备份计算机。尽管双启动设置过程不是很复杂，但是仍然可能发生事故。因此，请花点时间备份您的重要..._windows linux双启动

【flink番外篇】1、flink的23种常用算子介绍及详细示例（1）- map、flatmap和filter_flink 常用的分类和计算-程序员宅基地

文章浏览阅读1.6w次，点赞25次，收藏20次。本文主要介绍Flink 的3种常用的operator（map、flatmap和filter）及以具体可运行示例进行说明.将集合中的每个元素变成一个或多个元素,并返回扁平化之后的结果。按照指定的条件对集合中的元素进行过滤,过滤出返回true/符合条件的元素。本文主要介绍Flink 的3种常用的operator及以具体可运行示例进行说明。这是最简单的转换之一，其中输入是一个数据流，输出的也是一个数据流。下文中所有示例都是用该maven依赖，除非有特殊说明的情况。中了解更新系统的内容。中了解更新系统的内容。_flink 常用的分类和计算

（转）30 IMP-00019: row rejected due to ORACLE error 12899-程序员宅基地

文章浏览阅读590次。IMP-00019: row rejected due to ORACLE error 12899IMP-00003: ORACLE error 12899 encounteredORA-12899: value too large for column "CRM"."BK_ECS_ORDER_INFO_00413"."POSTSCRIPT" (actual: 895, maximum..._row rejected due to oracle