思路

如果直接计算 $a * b$ 会超过 $long \\ long$ 的最大范围 （long long ：2^64 - 1 约为 9 * 10^18）
所以采用快速加（类似于快速幂的思想）
把 b写成二进制形式，然后如果某位上为1 就加上它a*（2^n）次方 （n是当前的的位置）
然后 b >> 1（b右移一位）
（别忘记取模）

例： 3 * 4 % 5
b = 4 = 0100

3 * (2^0) = 3
3 * (2^1) = 6
3 * (2^2) = 12  √
3 * (2^3) = 24  

=> res = (0 + 12) % 5 = 2 

if (b & 1)：b的末尾是1，res 就加上 当前的 a 

快速加

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

    return res;
}

顺便复习一下快速幂

快速幂

LL qmi(LL a, LL b, LL c)
{
    LL res = 1;
    while(b)
    {
        if (b & 1) res = (res * a) % p;
        a = (a * a ) % p;
        b >>= 1;
    }
    return res;
}

code:

#include<cstdio>

using namespace std;

typedef long long LL;

LL qadd(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;
    scanf("%lld%lld%lld", &a, &b, &p);

    printf("%lld\n", qadd(a, b, p));

    return 0;
}