《算法竞赛入门经典》64位整数乘法--题解

题目描述：
求 a 乘 b 对 p 取模的值，其中 1 <= a,b,p <= 10^18

输入描述:
第一行a，第二行b，第三行p。

输出描述:
一个整数，表示a * b mod p的值。

实例：
输入： 2 3 9
输出： 6

思想：
这道题是要先算出a*b再对其结果进行求模（取余），因为a和b的最大值为1e+18，我们知道乘法有的时候会溢出，即使是 longlong 也可能在乘法时爆掉。所以我们寻找一种能高效完成乘法操作并且不会爆 longlong 的算法，也就是快速乘。

代码原理
可以把 a * b这样算：
a * b = a + a + a + ...+ a
而
a * 1 = a
a * 2 = 2a
a * 4 = 4a
a * 8 = 8a
...
所以可以推出：
a * (2 ^ k) = 2 ^ k * a

完整AC代码如下：

#include <iostream>

using namespace std;

typedef long long ll;// 给long long类型起别名：ll类型，为了方便

int main()
{

    ll a, b, p;
    ll ans = 0;//初始化最终的答案

    cin >> a >> b >> p;

    while (b != 0)//(b != 0)也可以直接写成(b)因为当b为0时将结束循环
    {
        if ((b & 1) != 0)//若b二进制的第一位为1时，将返回1否则返回0
        {
            ans = (ans + a) % p;
        }
        a = (a * 2) % p;
        b >>= 1;//将b的二进制去掉第一位，同b = b >> 1这样写是为了方便
    }

    cout << ans << endl;

    return 0; 
}