64位整数乘法

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

输入格式

三个整数 $a,b,p$

输出格式

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

数据范围

$0\leqslant a,b\leqslant 10^{18} $

$1\leqslant p\leqslant 10^{18}$

输入样例：

3 4 5

输出样例：

2

解析

（默认懂位运算，不懂的查）

和上一道题一样，不过这次不是超时，而是爆longlong。

同理，用数学常识将 $b$ 分解，不再多解释 放代码

#include <cstdio>
#include <iostream>

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