AcWing 90. 【位移运算】64位整数乘法
原题链接
简单
作者:
潘达达
,
2023-08-05 14:03:02
,
所有人可见
,
阅读 75
/*
取模运算法则:
(a + b) % p = (a % p + b % p) % p
(a * b) % p = ((a % p) * (b % p)) % p
a * 1 = a
a * 2 = 2a
a * 4 = 4a
a * 8 = 8a
...
a * (2^k) = (2^k)a
Trick:
1. 64位int是10^19,所以10^18相加,不会超;
2. 理解下取模的加法运算
*/
#include <iostream>
typedef unsigned long long ULL;
using namespace std;
int main()
{
ULL a, b, p;
cin >> a >> b >> p;
ULL res = 0;
while (b) {
if (b & 1) res = (res + a) % p;
b >>= 1;
a = 2 * a % p;
}
cout << res << endl;
return 0;
}