CH 0102 64位整数乘法【快速幂思想 | 数学】
- 作者: 糖宝宝ing
- 来源: 51数据库
- 2021-07-31
题目链接
题目描述：
求 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?1?2k?1+ck?2?2k?2+...+c0?20
那么：
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;
}
