算法题：64位整数乘法

问题描述

求 a 乘 b 对 p 取模的值，其中 1≤a,b,p≤10¹⁸。

输入格式

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

输出格式

一个整数，表示(a*b) mod p的值。

样例

输入

2
3
9

输出

6

解决方案

代码

#include <iostream>

using namespace std;

long long fun(long long a, long long b, long long p) {
    long long sum = 0;

    while (b) {
        if (b & 1) {
            sum += a;
            sum %= p;
        }

        a *= 2;
        a %= p;
        b >>= 1;
    }

    return sum;
}

int main() {
    long long a, b, p;
    cin >> a >> b >> p;

    cout << fun(a, b, p);

    return 0;
}