AcWing 90. 64位整数乘法
原题链接
简单
作者:
喜欢可爱猫猫
,
2023-10-09 10:35:06
,
所有人可见
,
阅读 54
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
/**
快速幂:求a^k mod p 的结果
核心技巧:反复平方法,乘法实现乘方
int qmi(int a, int k, int p)
{
int res = 1;
while (k)
{
if (k & 1) res = res * a % p;
a = a * a % p;
k >>= 1;
}
return res;
}
*/
// vs
/**
long long : 9 * 10^18
龟速加:加法实现乘法
思路:避免两个数相乘,
暴力:把a加b次,每次modp,但是时间复杂度为O(b)
优化:用二进制把b凑出来
*/
typedef long long LL;
LL qadd(LL a, LL b, LL p)
{
LL res = 0;
while (b)
{
if (b & 1) res = (res + a) % p;
a = (a + a) % p;
b >>= 1;
}
return res;
}
int main()
{
LL a,b,p;
scanf("%lld%lld%lld", &a, &b, &p);
printf("%lld\n", qadd(a,b,p));
return 0;
}