一.題目描述:
N<k時,root(N,k) = N,否則,root(N,k) = root(N',k)。N'為N的k進制表示的各位數字之和。輸入x,y,k,輸出root(x^y,k)的值 (這裡^為乘方,不是異或),2=<k<=16,0<x,y<2000000000,有一半的測試點裡 x^y 會溢出int的範圍(>=2000000000)
輸入:
每組測試資料包括一行,x(0<x<2000000000), y(0<y<2000000000), k(2<=k<=16)
輸出:
輸入可能有多組資料,對于每一組資料,root(x^y, k)的值
樣例輸入: 4 4 10
樣例輸出: 4
二.題目分析
(1)采用直接模拟的方式,先計算X^Y,然後在進制轉換,但是大資料(x^y)将超出範圍。
(2)數學公式推導
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiIyVGduV2QvwVe0lmdhJ3ZvwFM38CXlZHbvN3cpR2Lc1TPB10QGtWUCpEMJ9CXsxWam9CXwADNvwVZ6l2c052bm9CXUJDT1wkNhVzLcRnbvZ2LcZXUYpVd1kmYr50MZV3YyI2cKJDT29GRjBjUIF2LcRHelR3LcJzLctmch1mclRXY39TMzcDO1IDM1EzMygDM1EDMy8CX0Vmbu4GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.jpg)
由上述分析,我們希望找到Nr=N%(k-1)。
當Nr等于0時,處于邊界條件,Nr=k-1。
(3)關于快速幂的計算
二分求幂參考:http://blog.csdn.net/prstaxy/article/details/8740838
快速幂取模參考:http://blog.sina.com.cn/s/blog_8619a25801010wcy和http://blog.csdn.net/yangyafeiac/article/details/8707079
三.代碼
#include <stdio.h>
#include <stdlib.h>
long long QuickPow(long long n,long long base,long long k)
{
long long ans=1;
while(n)
{
if(n&1)
ans=(base*ans)%k;
base =(base*base)%k;
n>>=1;
}
return ans;
}
int main()
{
long long x,y,k,z;
while(scanf("%lld%lld%lld",&x,&y,&k)!=EOF)
{
z=QuickPow(y,x,k-1);
if(z==0)
z=k-1;
printf("%lld\n",z);
}
return 0;
}