欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

快速幂取余运算

程序员文章站 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;
}