python/TangDou/AcWing_TiGao/T6/WeiYunSuan/90.md

##AcWing 90. 64位整数乘法

一、题目描述

求 a 乘 b 对 p 取模的值。

输入格式 第一行输入整数a，第二行输入整数b，第三行输入整数p。

输出格式 输出一个整数，表示a*b mod p的值。

数据范围 1≤a,b,p≤10^{18}

输入样例：

3
4
5

输出样例：

2

二、解题思路

long long的最大值：9223372036854775807,最多是19位。

啊？最多才19位,那坏了！因为a是最大10^{18},也就是19位,如果直接a*a,直接就爆炸了！没机会再取模了！

那咋办？

不能用a*a呗！我们可以想办法(a+a)\%p,因为a+a不会冒出long long上限，然后再通过(a+a)\%p的值拼装出a^b。

res=a+a就是两两的算，然后是不是可以用res再翻一下翻最终计算出来呢？

这是可以的，因为这就是 二进制 的思想嘛。

先看例子：计算 3^5

\large 3^5=3^4*1+3^2*0+3^1*1

噢，就是把5按二进制的思路进行拆分成5=4+1,也就是(101)_2 然后从后往前，看到每一位是数字1还是数字0,不管是1还是0，翻番的base要一路跟上，因为本位为0就需要base,否则不加base。

加完了之后别忘了取模，防止冒了！

有同学可能在思考，那要是base在加的过程中冒了怎么办呢？ 因为base是为了最终的结果res而努力累加的，最终算完 res再取模，与在计算过程中取模，是符合加法取模规则的，即(a+b)\%p=(a\%p + b\%p)\%p

所以，谁有可能在计算过程中冒了，就把谁取模掉就对了！

三、龟速乘

龟速乘：把能很快完成的乘法，变成二进制分解后的加法，在加的过程中进行取模，可以防止计算过程中的溢出。

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
LL a, b, p, res;

int main() {
    cin >> a >> b >> p;

    // 龟速乘
    while (b) {
        if (b & 1) res = (res + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }

    cout << res << endl;
    return 0;
}

四、__int128解法

#include <bits/stdc++.h>

using namespace std;

/*
NOIP
CCF 组织的赛事都可以了
__int128取值范围−2^127~2^127−1
__int128只能通过字符形式输入输出
*/
typedef long long LL;

LL a, b, p, res;

int main() {
    cin >> a >> b >> p;
    cout << (LL)(__int128(a) * (__int128)b % p) << endl;
    return 0;
}