浅析 NC23046 华华教月月做数学 （快速幂、快速乘）

题目链接：

https://ac.nowcoder.com/acm/problem/23046

题面：

找到了心仪的小姐姐月月后，华华很高兴的和她聊着天。然而月月的作业很多，不能继续陪华华聊天了。华华为了尽快和月月继续聊天，就提出帮她做一部分作业。 月月的其中一项作业是：给定正整数A、B、P，求 $A^B\mathrm{m}\mathrm{o}\mathrm{d}PA^B\; \backslash mod\; P$ 的值。华华觉得这实在是毫无意义，所以决定写一个程序来做。但是华华并不会写程序，所以这个任务就交给你了。 因为月月的作业很多，所以有T组询问。

输入描述:
第一行一个正整数T表示测试数据组数。
接下来T行，每行三个正整数A、B、P，含义如上文。

输出描述:
输出T行，每行一个非负整数表示答案。

input:
2
2 5 10
57284938291657 827493857294857 384729583748273

output:
2
18924650048745

数据范围:
1≤T≤10^3
1≤A,B,P≤10^18

分析：

本题求 a 的 b 次方 模 p 的值，本质就是求快速幂。 由数学知识可知：(a * b) mod p = (a mod p) * (b mod p) mod p 。那么就可以将$\mathrm{（}ab\mathrm{）}\mathrm{m}\mathrm{o}\mathrm{d}p（ab）\; \backslash mod\; p$ 转换为若干$a^k\mathrm{m}\mathrm{o}\mathrm{d}pa^k\; \backslash mod\; p$ (k = 2n) 的乘积。这一操作在二进制上进行,可以利用位运算实现。
观察数据范围，发现乘法可能会越界，所以要手动实现乘法，保证相乘的两个数在乘法运算过程中都不越界（按位边乘边取模），即 龟速乘。

long long
所占内存大小：8byte=64bit；
所能表示范围：-9223372036854775808~9223372036854775807
(即-2^63 ~ 2^63-1)
(即-9*10^18 ~ 9*10^18)

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long 

using namespace std;

// 快速乘法 （龟速乘）
ll quick_multiply(ll x, ll y, ll p) {
	ll multi = 0;
	while (y) {
		if (y&1) 
			multi = (multi + x) % p;
		x = (x << 1) % p;
		y >>= 1;
	}
	return multi;
}

// 快速幂
ll quick_pow(ll a, ll b, ll p) {
	
	ll ans = 1;
	while (b) {
		if (b & 1) 
			ans = quick_multiply(ans, a, p);
		b >>= 1;
		a = quick_multiply(a, a, p);
	}
	return ans;
	
}


int main () {
	std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int t = 1;
	cin >> t;
	
	ll a, b, p;
	
	while (t--) {
		cin >> a >> b >> p;
		cout << quick_pow(a, b, p) << endl;
	}
	
	return 0;
	
}

补充知识：

C++ pow() 函数计算缓慢的原因： https://stackoverflow.com/questions/41072787/why-is-powint-int-so-slow

摘选可能的解释：

1. pow是函数，传递参数，调用函数的代价远大于直接相乘。 并且，调用函数破坏了cpu的分支预测和缓存优化

2. ans = pow(int x, int y)函数要先把int转换为double函数，然后利用 $ans=e^{y\ln x}ans\; =\; e^\{y\; \backslash ln\; x\}$ 进行运算，因此速度会慢。