题目大意:
求 $a$ 乘 $b$ 对 $p$ 取模的值。
解题方法:
这道题和上一道题非常的像啊!
可以看看上一题我的题解:题解
唯一的区别就在于一个是 乘方,一个是 乘。
这题还要用类似快速幂的思想,我们来看一下快速幂的板子:
int qmi(int a, int k, int p) // 求a^k mod p
{
int res = 1 % p;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
我们来观察一下,里头对于答案的更新的位置,从 $b$ 个 $a$ 乘 在一起,变成了 $b$ 个 $a$ 加 在一起。
好这一行就变成了这样:
if (k & 1) res = (LL)(res + a) % p;
好我们在来观察下一行:
a = (LL)a * a % p;
我们看一下这个 $a$ 的实际含义:我们就是 $x^1$ 、$x^2$、$x^4$……这些东西。那么现在就应该变成 $x$, $2x$, $4x$......每次就应该变成a = (LL)a * 2 % p
就这样,这题就搞定了。
完整代码,时间复杂度:$O(\log n)$
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL a, b, p;
LL ans = 0;
int main()
{
cin >> a >> b >> p;
while (b) {
if (b & 1) ans = (ans + a) % p;
a = (a + a) % p;
b >>= 1;
}
cout << ans << endl;
return 0;
}
orz
看了一圈还是这个解释最好理解
Orz
orz
Orz