牛客-996C 64位整数乘法（快速幂）

链接：https://ac.nowcoder.com/acm/contest/996/C

题目描述

求 a 乘 b 对 p 取模的值，其中$1 \leq a,b,p \leq 10^{18}$。

输入描述:

第一行a，第二行b，第三行p。

输出描述:

一个整数，表示$a \times b \bmod p$的值。

示例1

输入

2
3
9

输出

6

---

#include <bits/stdc++.h>

using namespace std;

long long calculate(long long a, long long b, long long p)
{
    long long res = 0;
    while (b) {
        if (b & 1) res = (res + a) % p;
        a = a * 2 % p;
        b >>= 1;
    }

    return res;
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    long long a, b, p;
    cin >> a >> b >> p;

    cout << calculate(a, b, p) << endl;

    return 0;
}