题目描述

求 a 乘 b 对 p 取模的值。第一行输入整数a，第二行输入整数b，第三行输入整数p。

输入样例

2 4 5

输出样例

2

算法1

(快速幂) $O(logb)$

题解同89，注释较为详细

时间复杂度分析：每次对b进行右移操作

C++ 代码

/*
    Name:AcWing 90. 64位整数乘法
    Author:wyz
    Date:2019/3/31 9:08:24
    Note:

*/

#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
int main(){
    //范围用ll即可
    ll a,b,p,res;
    cin>>a>>b>>p;
    res=0;//因为是加法，所以这里初始化为0，而不是1，显然res=0就无需mod p 
    while(b){
        if(b&1)res=(res+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    cout<<res<<endl;


    return 0;
}