时间限制: 1
s
空间限制: 128000
KB
题目等级
: 钻石
Diamond
题解
查看运行结果
题目描述 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
数据范围及提示 Data
Size & Hint
分类标签 Tags 点此展开
分治 快速幂 数论
w
分析：本题主要的难点在于数据规模很大（b，p都是长整型数），对于b^p显然不能死算，那样的话时间复杂度和编程复杂度都很大。
w
下面先介绍一个原理：A*B%K
= (A%K )*(B% K )%K。显然有了这个原理，就可以把较大的幂分解成较小的，因而免去高精度计算等复杂过程。那么怎样分解最有效呢？
显然对于任何一个自然数P，有P=
P/2* 2 + P%2，如19=2
* 19/2 + 19%2=2*9+1，利用上述原理就可以把B的19次方除以K的余数转换为求B的9次方除以K的余数，即B19=B2*9+1=B*B9*B9，再进一步分解下去就不难求得整个问题的解
代码：
#include
using namespace std;
#include
long long f(long long );
long long b,k;
int main()
{
long long p;
cin>>b>>p>>k;
cout<<b<<"^"<<p<<" mod
"<<k<<"=";//输出的格式
b%=k;//不能放在前面，那么b的只就不对了
b=f(p);
cout<<b;
return 0;
}
long long f(long long p)
{
if(p==0) return 1;//b^0%k==1,这是递归的边界
long long tmp=f(p/2)%k;
tmp=tmp*tmp%k;
if(p%2==1) tmp=(tmp*b)%k;//因为在main已经有了b%=k了，所以这里乘以b不用再%k了
return tmp;//tmp储存的是当前的b^p%k的值，传回上一层函数再平方
}
//2^10 mod 9=7