root(N,k)
求root(N, k)
http://www.nowcoder.com/questionTerminal/9324a1458c564c4b9c4bfc3867a2aa66
①首先是由于x^y可能很大，会超时，所以用快速幂算法。
如果y是偶数，那么指数减半底数平方；如果y是奇数，那么给最终的结果乘上x的一次方，这样能够求出x^y的结果res。
②再来看root（N，k），根据题意有N = a0 + a1*k + a2*k^2 +...
N' = a0 + a1 + a2+ ...
两式相减能够得到N-N'被k-1整除。
所以N' = N%(k-1)，但由于N'是在[0,k-1]之中，而N' = k-1这种情况会在N%(k-1)中算为0，所以加一个条件判断。
③quickpow 中还利用了数学上的定理(x * y) % k = (x % k) * (y % k) % k
#include<stdio.h>
long long quickpow(long long x,long long y,int k) // 快速幂
{
long long res = 1;
while(y)
{
if(y%2)
res = res *x % (k-1);
x = x*x %(k-1);
y /=2;
}
return res;
}
void root(long long x,long long y,int k)
{
long long res;
res = quickpow(x,y,k);
printf("%d",res?res:k-1);
}
int main()
{
long long x,y;
int k;
scanf("%lld%lld%d",&x,&y,&k);
root(x,y,k);
return 0;
}
查看15道真题和解析