很显然，\(10^{18} * 10^{18}\)已经超出了c++可存整数范围的，我们不可以通过直接相乘取模，那么根据二进制的“倍增”思想，我们按下拆分。

对于

\(a * b = a * (\sum_{i=0}^{k-1}c_i2^i)\)
同理，有\(a * 2^i = a * 2^{i-1} * 2\) 根据取模的性质

(a + b) % p = (a % p + b % p) % p

对于\(a * 2^{i-1} * 2 mod p\) 运算过程的每一步都不会超过\(2*10^{18}\),完全在可接受的范围内。那么为什么运算过程的每一步都不会超过\(2*10^{18}\)呢？

首先，a是一个不超过\(10^{18}\)的正整数，而p也为不超过不超过\(10^{18}\)的正整数，也就是说如果a经过*2操作之后超过了\(10^{18}\)那么经过取模之后则为一个较小的数，而这样取模是符合取模的性质的。而整个操作中所产生最大的数即a为\(10^{18}\)乘2后为\(2 * 10^{18}\)

#include <iostream>
using namespace std;

int main(){
    long long a,b,p,ans;
    cin >> a >> b >> p;
    for (;b; b >>= 1){
        if (b & 1){
            ans = (ans + a) % p;
        }
        a = a*2 % p;
    }
    cout << ans;
}