AcWing 90. 64位整数乘法

题目描述

求 a 乘 b 对 p 取模的值。

输入格式
第一行输入整数a，第二行输入整数b，第三行输入整数p。

输出格式
输出一个整数，表示a*b mod p的值。

数据范围
1≤a,b,p≤1018

输入样例

3
4
5

输出样例

2

思想:快速幂,把b用二进制表示

1.计算3*10：
10用二进制表示为1010，所以3*10=3*8+3*2
2.计算3*5：
5用二进制表示为101,所以3*5=3*4+3*1

c++代码

#include<bits/stdc++.h>
using namespace std;
long long a,b,p;//超出了int范围，要用long long
int main()
{
    scanf("%lld%lld%lld",&a,&b,&p);
    long long ans=0;
    while(b)
    {
        if(b&1) ans=(ans+a)%p;//如果b二进制表示的个位是1,,就进行相加
        a=a*2%p;//预处理出a*1,a*2,a*4……a*(2^k)
        b=b>>1;//将b的个位舍去
    }
    printf("%lld",ans);
    return 0;
}