CH102 64位整数乘法

求 a 乘 b 对 p 取模的值。

输入格式

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

输出格式

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

数据范围

$$ 1≤a,b,p≤ 10^{18}$$

输入样例：

3
4
5

输出样例：

2

很显然，$10^{18} * 10^{18}$已经超出了c++可存整数范围的，我们不可以通过直接相乘取模，那么根据二进制的“倍增”思想，我们按下拆分。

对于

$a * b = a * (\sum_{i=0}^{k-1}c_i2^i)$
同理，有$a * 2^i = a * 2^{i-1} * 2$ 根据取模的性质

(a + b) % p = (a % p + b % p) % p

对于$a * 2^{i-1} * 2 mod p$ 运算过程的每一步都不会超过$2*10^{18}$,完全在可接受的范围内。那么为什么运算过程的每一步都不会超过$2*10^{18}$呢？

首先，a是一个不超过$10^{18}$的正整数，而p也为不超过不超过$10^{18}$的正整数，也就是说如果a经过*2操作之后超过了$10^{18}$那么经过取模之后则为一个较小的数，而这样取模是符合取模的性质的。而整个操作中所产生最大的数即a为$10^{18}$乘2后为$2 * 10^{18}$

#include <iostream>
using namespace std;

int main(){
    long long a,b,p,ans;
    cin >> a >> b >> p;
    for (;b; b >>= 1){
        if (b & 1){
            ans = (ans + a) % p;
        }
        a = a*2 % p;
    }
    cout << ans;
}