快速幂取余运算

83 阅读 0 评论 55 点赞

我是靠谱客的博主简单鲜花，这篇文章主要介绍快速幂取余运算，现在分享给大家，希望可以做个参考。

题目描述 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位整数的范围，可以采用模运算来解决高精度计算。
快速幂算法：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*题解*/
#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;
}