【刷题】基础算法——位运算：64位整数乘法

【刷题】基础算法——位运算：64位整数乘法

题目链接

这题的a和b相乘会超过longlong的范围，由于模运算符合分配律，因此可以将 b b b拆成二进制与 a a a相乘。

比较暴力的做法就是，对b的从第到高的第i位，都算出来a * 2^i % p 的值
例如 a * 2^3 = (((a * 2 %p) * 2 % p) * 2 % p)
然后再加到ans里。

#include 
using namespace std;

long long a, b, p;

int main() {
	scanf("%lld%lld%lld", &a, &b, &p);
	long long ans = 0, tmp;
	int k = 0;
	while (b) {
		int b1 = b & 1;
		b >>= 1;
		
		tmp = a * b1;
		for (int i = 1; i <= k; i ++ ) {
			tmp = (tmp * 2) % p;
		}
		
		ans = (ans + tmp) % p;
		
		k ++ ;
	} 
	printf("%lldn", ans);
	return 0;
}

仔细观察发现完全可以去掉这个从1到k的循环，只需在while循环内令a也跟着*2即可

#include 
using namespace std;

long long a, b, p;

int main() {
	scanf("%lld%lld%lld", &a, &b, &p);
	long long ans = 0;
	while (b) {
		ans = (ans + (a * (b & 1))) % p;
		b >>= 1;
		a = (a * 2) % p;
	} 
	printf("%lldn", ans);
	return 0;
}