题目描述 当 $N < k$ 时，$root(N, k) = N$，否则，$root(N, k) = root(N', k)$。 $N'$ 为 $N$ 的 $k$ 进制表示的各位数字之和。 输入 $x$, $y$, $k$，输出 $root(x^y, k)$ 的值（这里 $^$ 为乘方，不是异或），$2 \leq k \leq 16$，$0 < x, y < 2000000000$，有一半的测试点里 $x^y$ 会溢出 $int$ 的范围（$\geq 2000000000$） 输入格式 每组测试数据包括一行，$x$ ($0 < x < 2000000000$), $y$ ($0 < y < 2000000000$), $k$ ($2 \leq k \leq 16$) 输出格式 输入可能有多组数据，对于每一组数据，$root(x^y, k)$ 的值 输入样例 4 4 10 输出样例 4