64位整数乘法

64位整数乘法

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

输入格式

三个整数 $a,b,p$

输出格式

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

数据范围

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

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

输入样例:

1
3 4 5

输出样例:

1
2

解析

(默认懂位运算,不懂的查)

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
#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;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!