龟速乘学习笔记

发表于 更新于 分类于

快速幂死了该用什么替代呢（嘻嘻），本文介绍龟速乘的原理及使用（内附代码实现）。

背景

关于快速幂：
它死了。
咳咳。
以下是快速幂模板：

1
2
3
4
5
6
7
8
9
10
11
inline int q_p(int a, int k, int p) 
{
	int ans = 1;
	while (k) 
	{
		if (k & 1)ans = ans * a % p;
		k >>= 1;
		a = a * a % p;
	}
	return ans;
}

可以看出，快速幂有一个缺点：当模数 p 大于 int 范围（最大值为 231−12^{31}-1）时，快速幂会爆 long long。
此时解决 ab mod ca^{b} \bmod c 的问题时就无法用快速幂了。
于是，龟速乘应运而生。

龟速乘

原理

通过将 乘法 转化为 加法并每次取模 而避免了爆 long long。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//龟速乘
inline int q_m(int a, int k, int p)
{
	int ans = 0;
	while (k)
	{//    区别在这里 ↓
		if(k & 1)ans += a, ans %= p;
		k >>= 1;
		a = a + a, a %= p;
		//和这里 ↑
	}
	return ans;
}
//快速幂
inline int q_p(int a, int k, int p) 
{
	int ans = 1;
	while (k) 
	{
		if (k & 1)ans = q_m(ans, a, p), ans %= p;
		k >>= 1;
		a = q_m(a, a, p), a %= p;
	}
	return ans;
}

速度

顾名思义，龟速乘会比系统的乘法慢一些。

OK就这样。
本蒟蒻新学 OI ，如有错误请 D 我。