CH 0102 64位整数乘法【快速幂思想 | 数学】
题目描述：
求 a 乘 b 对 p 取模的值，其中 1 ≤ a, b, p ≤ 1 0 18 10^{18} 1018。
题解：
我们观察到，乘的时候很容易爆long long，我们又看到数据范围比较特别，
1
0
18
10^{18}
1018 乘以2后也没到
2
63
−
1
2^{63} - 1
263−1 (9.2233720368548e+18)，所以我们可以把 b 利用类似于快速幂的思想用二进制表示，即：
b
=
c
k
−
1
2
k
−
1
+
c
k
−
2
2
k
−
2
+
.
.
.
+
c
0
2
0
b=c_{k-1}2^{k-1}+c_{k-2}2^{k-2}+...+c_{0}2^{0}
b=ck−12k−1+ck−22k−2+...+c020
那么：
a
∗
b
=
a
∗
c
k
−
1
∗
2
k
−
1
+
a
∗
c
k
−
2
∗
2
k
−
2
+
.
.
.
+
a
∗
c
0
∗
2
0
a*b=a*c_{k-1}*2^{k-1}+a*c_{k-2}*2^{k-2}+...+a*c_{0}*2^{0}
a∗b=a∗ck−1∗2k−1+a∗ck−2∗2k−2+...+a∗c0∗20
因为
a
∗
2
i
=
(
a
∗
2
i
−
1
)
∗
2
a*2^i=(a*2^{i-1})*2
a∗2i=(a∗2i−1)∗2，若已求出
a
∗
2
i
−
1
m
o
d
p
a*2^{i-1}\mod{p}
a∗2i−1modp，则计算
(
a
∗
2
i
−
1
)
∗
2
m
o
d
p
(a*2^{i-1})*2 \mod{p}
(a∗2i−1)∗2modp 时，运算过程中每一步的结果都不超过
2
∗
1
0
18
2*10^{18}
2∗1018，仍然在long long范围内，所以很容易通过 k 次递推求出每个乘积项。当
c
i
=
1
c_i=1
ci=1时，把该乘积项累加到答案中即可。
AC codes：
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
//#include <unordered_set>
//#include <unordered_map>
#include <deque>
#include <list>
#include <iomanip>
#include <algorithm>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
//#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
//cout << fixed << setprecision(2);
//cout << setw(2);
const int N = 2e5 + 6, M = 1e9 + 7;
int main() {
//freopen("/Users/xumingfei/Desktop/ACM/test.txt", "r", stdin);
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
ll a, b, p;
cin >> a >> b >> p;
ll ans = 0;
while (b) {
if (b & 1) ans = (ans + a) % p;
a = a * 2 % p;
b >>= 1;
}
cout << ans << '\n';
return 0;
}
本文地址：https://blog.csdn.net/weixin_44258590/article/details/108737734