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