AcWing 89 a^b
发布日期:2021-05-28 16:29:42 浏览次数:22 分类:精选文章

本文共 615 字,大约阅读时间需要 2 分钟。

这道题目是关于快速幂算法的实现,主要需要注意的是测试用例中当模数p为1时的情况。在这种情况下,任何数对1取模都会得到0,因此在快速幂函数中,初始值ans应设为0 % p。

以下是实现代码:

#include 
using namespace std;typedef long long ll;ll binaryPow(ll a, ll b, ll p) { ll ans = 1 % p; // 初始化为1 % p while (b > 0) { if (b & 1) { ans = (ans * a) % p; // 如果b的最低位是1,则ans乘以a并对p取模 } a = (a * a) % p; // a平方后对p取模 b >>= 1; // b右移1位,相当于整除以2 } return ans;}int main() { int a, b, p; cin >> a >> b >> p; cout << binaryPow(a, b, p) << endl;}

需要注意的是,在实现快速幂算法时,这里的初始值需要特别处理。如果模数p为1,那么无论a和b的值是什么,最终结果都应该是0。因此在初始化时,应将ans设为1 % p,这样当p=1时,会自动变为0,符合预期结果。

上一篇:AcWing90 64位整数乘法
下一篇:POJ2586 Y2K Accounting Bug

发表评论

最新留言

第一次来,支持一个
[***.219.124.196]2025年04月17日 10时22分40秒