<= 求赞qwq,码字不易,你的支持是我写作的动力
宣传一下算法提高课题解合集
90.64位整数乘法
求 $a$ 乘 $b$ 对 $p$ 取模的值。
输入格式
第一行输入整数 $a$ ,第二行输入整数 $b$ ,第三行输入整数 $p$ 。
输出格式
输出一个整数,表示 a*b mod p
的值。
数据范围
$1 \le a,b,p \le 10^{18}$
错误的思路
观察题意,发现是简单的计算,考虑直接输出 a*b mod p
再观察数据范围,发现 $a \times b$ 就已经超过了 $long long$ 的数据范围
正解
我们考虑将 $b$ 进行二进制拆分:$b = 2 ^ {a_1} + 2 ^ {a_2} + 2 ^ {a_3} \cdots$
而乘法有乘法分配律,取余也有类似的性质
所以:$a \times b \mod p = (a \times 2 ^ {a_1} \mod p) + (a \times 2 ^ {a_2} \mod p) \cdots$
我们只要从小到大枚举 $a \times 2 ^ n$,当 $b$ 的二进制位含有 $2 ^ n$,答案加上 $a \times 2 ^ n \mod p$ 的值即可
c++ 代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100009;
ll a, b, p, ans = 0;
int main()
{
cin >> a >> b >> p;
while(b)
{
if(b & 1) ans = (ans + a) % p;//检查 b 的二进制位是否为1
b = b >> 1;//检查下一位
a = (a << 1) % p;//注意 a 也要 mod p
}
cout << ans << endl;
return 0;
}
不知道为啥 a 也要mod,防止越界mod a,不会影响后面的值吗?
不会,这就是mod的性质
a = (a << 1) % p;//注意 a 也要 mod p
请问这一步,取余的作用是什么?防治越界吗?
对的。
java包装类横扫一切