主要内容 #

1. 问题描述
2. 算法分析
3. 参考程序

1. 问题描述 #

输入b、p、k的值，求 b^p mod k的值。其中b、p、k、k*k为长整型数。
输入样例
2 10 9
输出样例
2^10 mod 9 =7
说明/提示
2^10 = 10242 1024 mod 9=7
数据规模与约定
对于100%的数据，保证 0 <= b,p < 2^31, 1 < k < 2 ^31

2. 算法分析 #

b, p 的取值范围：0 <= b,p < 2^31 ，不可能说将b ^ p 的数先计算出来再求余的，非常不现实。
还有一个知识点需要注意，即同余原理。
即 （a * b * c *…） % k
=( (a %k) * (b %k) * (c%k) … ) % k
例如：

显然有了这个原理，就可以把较大的幂分解成较小的，因而避免高精度计算等复杂的过程。那么如何分解最有效呢？显然对任何一个自然数p，有
p = 2 * p/2 + p%2，如19 = 2 * 19/2 + 19 % 2 = 2*9+1，利用上述原理就可以把b的19次方除以k的余数转化为求b的9次方除以k的余数，即b^19 = b^(2*9+1)=b*b^9*b^9，再进一步分解下去就不难得到问题的解。

3. 参考程序 #

#include <iostream>
#include <cstdio>
using namespace std;
long long k;
//取余运算的性质
//同余  (a * b) % k = ( (a % k) * (b * k) ) % k;
//(a * b * c) % k =  ((a % k) * (b % k) * (c % k))
long long fun(long long b, long long p)
{
    long long t;
    if (p == 0)//递归边界
        return 1;
     t = fun(b, p / 2) % k;
     //此语句无论是在if和else中都会执行，故直接放到f else 外面来
     
    if (p % 2 == 1)
    {
        return t * t * b % k;
    }
    else {
        return t * t % k;
    }
}
int main()
{
    long long b, p;
    cin >> b >> p >> k;
    cout << b << "^" << p << " mod " << k << "=" << (fun(b, p) % k)<< endl;
    return 0;
}