题目描述

64位整数乘法

求 a 乘 b 对 p 取模的值。
数据范围
1≤a,b,p≤10^18

样例

输入样例：
3
4
5
输出样例：
2

(二进制算法) $O(logn)$

C++ 代码

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
ll a,b,p,res=0;
int main()
{
    cin>>a>>b>>p;
    while(b)
    {
        if(b&1)res = (res+a)%p;//判断b的二进制最低位是不是1，如果是1，将a加进res最终结果里面
        a = a*2%p;//a^0,a^1,a^2,a^3...后面每一个结果都是前面结果的两倍，进行分部取余时对总结果取余不影响，
        //将a的结果乘以2，来进行下一步移位运算。
        b>>=1;//将b进行移位。
    }
    cout<<res<<endl;
    return 0;
}