N<k 时，root(N,k)=N，否则，root(N,k)=root(N′,k)。
N′ 为 N 的 k 进制表示的各位数字之和。
输入 x,y,k，输出 root(xy,k) 的值。
输入格式
输入包含多组测试数据。
每组数据占一行，包含三个整数 x,y,k。
输出格式
每组数据输出一行，root(xy,k) 的值。
数据范围
每个输入最多包含 100 组测试数据。
0<x,y<2×109,
2≤k≤6,
注意 xy 可能会溢出 int 范围。
输入样例：
4 4 10
输出样例：
4
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL x,y,k;
LL qmi()
{
LL res = 1;
while(y)
{
if(y & 1) res = res * x % （k-1）;
x = x * x % （k-1）;
y >>= 1;
}
return res;
}
int main()
{
while(cin >> x >> y >> k)
{
LL res = qmi();
if(res) cout << res << endl;
else cout << k << endl;
}
return 0;
}
