- 题目描述：
-
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 这道题我苦思冥想了很久，最令我头疼的就是数据的范围，2000000000的2000000000次方该有多大，如何去计算?
每次都要求N的k进制表示的各位数字之和，那么一要取模，二要求除法，这么大的数怎么做。题目考的一定不是大数的运算，肯定存在某种规律，那么这种规律是什么？ 在思考的过程中，首先考虑了 1. (a*b)mod N = (a * (b mod N)) mod N;
其次也考虑到了每次都要求N的k进制表示的各位数字之和,那么最后的那个和就是 2. N mod (k-1) (这个是凭找规律看出来的) 但接下来自己的思路就比较混乱，不知道该怎么处理x的y次方的问题，想了很久也没有想出来。 最后忍不住看了看其他人的题解，
他们确实求了x的y次方，而且用的是反复平方法来求，并且在求的过程中直接做取模运算，避免了数据溢出。差距就在这里。
代码如下#include <cstdio>
#include <cstring> typedef long long ll; int root(ll x, ll y, ll k) {
ll mi = ;
while (y) {
if (y & ) {
mi = (mi*x) % k;
}
x = (x * x)%k;
y = y >> ;
}
return mi;
} int main() {
ll x, y, k;
while (scanf("%lld %lld %lld", &x, &y, &k) != EOF) {
ll ans = root(x, y, k-);
if (ans == ) {
ans = k - ;
}
printf("%lld\n", ans);
}
return ;
}关于第2点
N=a0+a1*k+a2*k^+……an*k^n N'=a0+a1+a2+……+an N-N'=a1*(k-1)+a2*(k-1)^2+a3*(k-1)^3+......+an*(k-1)^n (N-N')%(k-1)=0 (N'-N'')%(k-1)=0 ..... (N(r-)-N(r))%(k-)= 相加得(N-N(r))%(k-)= N(r)=N%(k-) 故(x^y)%(k-)就是我们要求的。 当(x^y)%(k-)=0时，注意结果为k-