P10446 64位整数乘法

发表于

P10446 64位整数乘法

题目描述

求 $a$ 乘 $b$ 对 $p$ 取模的值。

输入格式

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

输出格式

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

输入输出样例 #1

输入 #1

1
2
3
3
4
5

输出 #1

1
2

说明/提示

$1 \le a,b,p \le 10^{18}$

思路分析 + 代码实现

注意到数据范围 $1 \le a,b,p \le 10^{18}$ ，这说明什么？结合 long long 的表示范围 $2^{63}-1 > 2 \times 10^{18}$ 可知，我们可以把 $a \times b$ 分解成 $a \times [\frac{b}{2} + \frac{b}{2} + (b \bmod 2)]$ 。因此我们可以写一个递归函数，结束递归的条件是 $b \leq 2$。复杂度为 $\operatorname{O}(nlogn)$ 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
long long solve(long long a, long long b, const long long mod) {
    if (b <= 2) return a * b % mod;
    if (b & 1) return (2 * solve(a, b >> 1, mod) % mod + a) % mod;
    return solve(a, b >> 1, mod) * 2 % mod;
}
int main() {
    long long a, b, p;
    cin >> a >> b >> p;
    cout << solve(a, b, p);
    return 0;
}