求a * b % p    1 ≤ a,b,p ≤ 10^18

long long 的范围大概是9 * 10^18

不用高精度
思路类似于快速幂

先算出
a % p
2a % p  =  2 * (a % p)
4a % p  =  2 * (2a % p)
8a % p  =  2 * (4a % p)
...
2^62 % p

-> 用左边的数把b凑出来
若b的二进制表示为11010 -> b = 2^1 + 2^3 + 2^4
把b中是1的位置对应的预处理的结果相加
a * b = a * 2^1 + a * 2^3 + a * 2^4

b的二进制表示最多有logb位
-> 时间复杂度为logb

#include <iostream>
using namespace std;

typedef long long LL; 

LL quick_add(LL a, LL b, LL p)
{
    LL res = 0;
    while ( b )
    {
        if ( b & 1 ) res = (res + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    LL a, b, p;
    cin >> a >> b >> p;
    cout << quick_add(a, b, p);
    return 0;
}