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

##[$AcWing$ $90$. $64$位整数乘法](https://www.acwing.com/problem/content/description/92/)
### 一、题目描述
求 $a$ 乘 $b$ 对 $p$ 取模的值。

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

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

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

**输入样例：**
```cpp {.line-numbers}
3
4
5
```
**输出样例：**
```cpp {.line-numbers}
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$

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

### 三、龟速乘

<font color='red' size=4><b>龟速乘：把能很快完成的乘法，变成二进制分解后的加法，在加的过程中进行取模，可以防止计算过程中的溢出。</b></font>

```cpp {.line-numbers}
#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$解法
```cpp {.line-numbers}
#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;
}
```