快速幂AcWing 89. a^b
求 $a$ 的 $b$ 次方对 $p$ 取模的值。
输入格式
三个整数 $a,b,p$ ,在同一行用空格隔开。
输出格式
输出一个整数，表示a^b mod p的值。
数据范围
$0 \le a,b \le 10^9$
$1 \le p \le 10^9$
输入样例：
3 2 7
输出样例：
2
快速计算$a^k\mod p$
- 实际上是把$k$表示成二进制$b_{\text{log}k}\cdots b_2b_1b_0$，因此$k=b_02^{2^0} + b_12^{2^1}+b_22^{2^2}+ \cdots b_{\text{log}k} 2^{2^{\text{log}k}}$
- 计算$a^k \mod p=a^{b_02^{2^0} + b_12^{2^1}+b_22^{2^2}+ \cdots b_{\text{log}k} 2^{2^{\text{log}k}}} \mod p=(a^{b_0 2^{2^0}}\mod p) \times (a^{b_1 2^{2^1}}\mod p) \times \cdots \times (a^{b_{\text{log}k} 2^{2^{\text{log}k}}}\mod p)$
- 此外迭代满足如下关系$2^{2^{i+1}} \mod p=(2^{2^{i}} \mod p)^2$
- 中间结果可能会溢出，要强制进行类型转换
- 时间复杂度$O(\text{log}k)$
$a^{b_i}=a×a×…×a$,暴力的计算需要O(n)的时间
快速幂使用二进制拆分和倍增思想，仅需要O(Iog)的时间。
对n做二进制拆分，例如，$3^{13}=3^{(1101)_2}=3^8·3^4·3^1$
对Q做平方倍增，例如，$3^1,3^2,3^4,3^8…$
n有logn+1个二进制位，我知道了$a^l,a^2,a^4,a^8,,a^{2logn}$后
只需要计算logn+1次乘法就可以了。
这里偷懒就用define int long long 了
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int qmi(int x, int k, int p) {
int res = 1;
while (k) {
if (k & 1) res = res * x % p;
x = x * x % p;
k >>= 1;
}
return res % p;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int a, b, p;
cin >> a >> b >> p;
cout << qmi(a, b, p) << endl;
return 0;
}
龟速乘AcWing 90. 64位整数乘法
题目
https://www.acwing.com/problem/content/description/92/
求 $a$ 乘 $b$ 对 $p$ 取模的值。
输入格式
第一行输入整数$a$，第二行输入整数$b$，第三行输入整数$p$。
输出格式
输出一个整数，表示a*b mod p的值。
数据范围
$1 \le a,b,p \le 10^{18}$
输入样例：
3
4
5
输出样例：
2
思路
与快速幂的思想一样，把乘法里面的b用二进制拆分，然后变成b个a相加
此外，还可以使用int128进行计算，但是需要注意强制类型转换
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
int mul(int a, int b, int p) {
int res = 0;
while (b) {
if (b & 1) res = (res + a) % p;
a = (a + a) % p;
b >>= 1;
}
return res;
}
int mul2(int a, int b, int p) {
__int128 aa = a, bb = b, pp = p;
__int128 res = aa * bb % pp;
return (int) res;
}
signed main() {
#ifndef ONLINE_JUDGE
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif
int a, b, p;
cin >> a >> b >> p;
cout << mul2(a, b, p);
return 0;
}
