求 a 乘 b 对 p 取模的值,其中 a,b,p 的取值范围为1 ≤ a,b,p ≤ 10^18 。

输入格式:

  • 第一行为 a 的值
  • 第二行为 b 的值
  • 第三行为 p 的值

输出格式:

  • 输出一行,表示 a×b mod p 的值。

输入样例:

2
3
9

输出样例:

6

题目分析

我们可以根据快速幂的思想,将 a * b 看成 ba 相加。

代码实现

#include <iostream>
using namespace std;
using LL = long long;

LL a, b, p;
LL multiolication(LL a, LL b, LL M) {
    LL ans = 0, t = a;
    while(b) {
        if(b & 1) ans = (ans + t)
        t = (t + t)
        b >>= 1;
    }
    return ans;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> a >> b >> p;
    cout << multiolication(a, b, p);
    return 0;
}

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status