快速幂取余运算
程序员文章站
2024-01-14 17:39:28
...
题目描述 Description
输入b,p,k的值,编程计算bp mod k的值。其中的b,p,k*k为长整型数(2^31范围内)。
输入描述 Input Description
b p k
输出描述 Output Description
输出b^p mod k=?
=左右没有空格
样例输入 Sample Input
2 10 9
样例输出 Sample Output
2^10 mod 9=7
本题题意理解并不难,只是让我们求解(b^p)%k;但是仔细看网页显示的通过率只要35%,应该明白此题并不是那么简单。
注意到题目的时间限制为1s,b,p,k均为长整形数,若用常规的如下求解幂运算的算法求解b^p的话很明显会超时:
typedef long long ll;
ll Pow(ll a, ll b) {
ll temp(1);
for (int i = 0; i < b; i++)
temp *= a;
return temp;
}
所以很明显在此使用更快的快速幂算法,具体快速幂的理解另有详解。
使用快速幂算法后,对于样例21000000007 2100000089 45987会出现WA的情况,结果是-32898,明显的是浮点数的溢出。
在程序设计竞赛中,如果计算结果超出了64位整数的范围,可以采用模运算来解决高精度计算。
快速幂算法:
ll pow(ll a, ll b) {
ll ans(1), base(a);
while (b != 0) {
if (b & 1 != 0)
ans *= base;
base *= base;
b >>= 1;
}
return ans;
}
改进后的快速幂算法:
ll pow(ll a, ll b) {
ll ans(1), base(a);
while (b != 0) {
if (b & 1 != 0)
ans = ans*base%k;
base = base*base%k;
b >>= 1;
}
return ans;
}
/*题解*/
#include<iostream>
typedef long long ll;
using namespace std;
long long b, p, k;
ll pow(ll a, ll b) {
ll ans(1), base(a);
while (b != 0) {
if (b & 1 != 0)
ans = ans*base%k;
base = base*base%k;
b >>= 1;
}
return ans;
}
int main()
{
cin >> b >> p >> k;
cout << b << "^" << p << " mod " << k << "=" << Pow(b, p) % k << endl;
system("pause");
return 0;
}
上一篇: 计算几何模板