問題描述
N<k時哨苛，root(N,k) = N，否則汁掠，root(N,k) = root(N',k)唠摹。N'為N的k進(jìn)制表示的各位數(shù)字之和。輸入x,y,k炎疆，輸出root(x^y,k)的值 (這里^為乘方卡骂，不是異或)，2=<k<=16形入，0<x,y<2000000000偿警，有一半的測試點里 x^y 會溢出int的范圍(>=2000000000)
輸入描述
每組測試數(shù)據(jù)包括一行，x(0<x<2000000000), y(0<y<2000000000), k(2<=k<=16)
輸出描述
輸入可能有多組數(shù)據(jù)唯笙，對于每一組數(shù)據(jù)螟蒸，root(x^y, k)的值
示例
- 輸入
4 4 10 - 輸出
4
分析推導(dǎo)
- 首先將 N用k進(jìn)制表示 展開：
N = a0 + a1 * k + a2 * k2 + ··· + a0 * kn
- 則盒使，N' 表示如下：
N' = a0 + a1 + a2 + ··· + an
- 則 N - N' 表示如下：
N - N' = a1 * (k - 1) + a2 * (k2 - 1) + ··· + an * (kn - 1)
- 證明 (N - N') % (k - 1) = 0
由等比數(shù)列求和公式有: 1 + k + k2 + ··· + kn - 1 = (1 - kn) / (1 - k)
∴ kn - 1 = (k - 1) * (1 + k + k2 + ··· + kn - 1)
∴ (kn - 1) % (k - 1) = 0
又∵ N - N' = a1 * (k - 1) + a2 * (k2 - 1) + ··· + an * (kn - 1)
∴ (N - N') % (k - 1) = 0
- 遞推歸納
令 N' = N1, N" = N2, ···
則有：
????(N - N1) % (k - 1) = 0
????(N1 - N2) % (k - 1) = 0
????...
????(Nr - 1 - Nr) % (k - 1) = 0
????其中 Nr 為我們要求的結(jié)果
將上面的各個遞推公式相加得到：
????(N - Nr) % (k - 1) = 0
∴ Nr = N % (k - 1)
- 得出結(jié)論
root(N, k) = N % (k - 1)
快速冪取模算法
算法實現(xiàn)
此算法實現(xiàn)基于上面數(shù)學(xué)推得到的結(jié)論，以及快速冪取模算法
#include <iostream>
using namespace std;
long root(long x, long y, int k){
long ans = 1;
k -= 1;
x %= k;
while(y != 0){
if(y & 1)
ans = (ans * x) % k;
y >>= 1;
x = (x * x) %k;
}
return ans == 0 ? k : ans;
}
int main(){
long x, y;
int k;
while(cin >> x >> y >> k)
cout << root(x, y, k);
}
