3388. 求root(N, k)

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;
}