[数据结构与算法]AcWing 90.64位整数乘法（题解）

题目链接：64位整数乘法

题目分析：题目求a乘b对p取模的值，乍一看很简单，但是事实不是如此。

第一步：分析题目数据范围。发现a,b,p都是可以取到10的18次方。所以我们预想一下最坏的情况就是a和b都取10的18次方。那么a·b等于10的36次方超过了超长整型long long 的数值范围。所以解决方法一：用高精度算法。方法二:用龟速乘

第二步：鉴于高精度算法代码较长所以我们选择用龟速乘算法。什么交龟速乘呢。龟速乘（快速加）和快速幂原理基本上一样。首先a·b我们可以把b写成几个数相加的结果。比如说3·7。7的二进制表示是111对应的是2的0次方+2的1次方+2的2次方。所以我们可以把3·7转换为3·（2的0次方+2的1次方+2的2次方）

第三步：总结一下，龟速乘虽然提高了时间复杂度。但是在面对数据范围较大的情况非常实用。

code:

#include<iostream>

using namespace std;

typedef long long ll;

ll a, b, p;

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()
{
    cin >> a >> b >> p;
    
    cout << qadd(a, b, p);
    
    return 0;
}