题目如图所示。这道题的难点在于x，y会溢出int的范围，所以我一开始想的是用大精度整数做，但是又要幂和模运算，那样就更麻烦了。所以我看了一下大佬的做法，发现了两种做法：二分求幂和快速模幂运算。
二分求幂：
首先介绍一下什么是二分求幂。如下图所示：
来看代码：
这是剑指offer的递归代码，名字起的怪怪的，不太想看哈哈
下面是王道机试指南的非递归
简单的举个例子就好懂了。
假设我要求2^10.那么就可以转化为2^5 * 2^5,然后2^5转化为2^2*2^2*2^1，继续下去就是2^1*2^1*2^1*2^1*2^1，这样就把一个大的数转化成口算出来的小数了，当然这个例子不是太好，如果举个大一点的数，就更好理解为什么要用二分求幂了。
了解了二分求幂后，来看这道题，首先这道题的精髓就在于接下来的分析，请仔细阅读：
对于root(N, k)中的N，我们可以把N看作关于k的多项式，也就是N = a0 + a1*k + a2*k^2 + … + an* k^n，而我们要求的root函数就是这个多项式的系数和，也就是a0 + a1 + a2 + ... + an。下面我们考虑root(N^2, k)。此时N^2 = (a0 + a1*k + a2*k^2 + … + an* k^n)^2，而这个多项式展开后的系数和是(a0 + a1 + a2 + … + an)^2，这个结果刚好就是先对N取root函数再平方的结果。实际上，我们很容易就能看出，多项式先乘方再取系数和(先乘再去掉k)与先取系数和再乘方(先去掉k再乘)，结果是一样的(因为有没有k并不影响系数间的相乘，也不影响相乘之后的求和)，于是乎，我们可以得到以下的递推公式：
root(x, y, k) = root((root(x, y / 2, k))^2, 1, k)， y为偶数
root(x, y, k) = root((root(x, y / 2, k))^2 * root(x, 1, k), 1,k),y为非1的奇数
root(x, 1, k) = x % k + x / k % k + ...(大于k的话再重复求root)
这和二分求幂的思想类似。来看代码
#include <stdio.h>
int root(int N,int k)
{
int sum;
while(N>=k)
{
sum=0;
while(N)
{
sum=sum+N%k;
N/=k;
}
N=sum;
}
return N;
}
int main()
{
int x,y,k;
while(scanf("%d%d%d",&x,&y,&k)!=EOF)
{
int sum=1;
int temp=root(x,k);
while(y)
{
if(y%2!=0)
sum=root(sum*temp,k);
temp=root(temp*temp,k);
y/=2;
}
printf("%d",sum);
}
}
快速模幂运算
对于快速模幂运算的介绍，我也是从一个博主哪里看到的。快速幂、快速幂取模的分析与代码实现 - iwts - CSDN博客
再看这道题的运用
由上述推导得出，问题就转化为求N%(k-1);这样就可以轻松的应用快速模幂运算了。代码我就不写了，主要是思想。
网友评论