3388. 求root(N, k)

题目描述

$N<k$ 时，$root(N,k) = N$，否则，$root(N,k) = root(N’,k)$。

$N’$ 为 $N$ 的 $k$ 进制表示的各位数字之和。

输入 $x,y,k$，输出 $root(x^y,k)$ 的值。

输入格式

输入包含多组测试数据。

每组数据占一行，包含三个整数 $x,y,k$。

输出格式

每组数据输出一行，$root(x^y,k)$ 的值。

数据范围

每个输入最多包含 $100$ 组测试数据。
$0 < x,y < 2 \times 10^9$,
$2 \le k \le 16$,
注意 $x^y$ 可能会溢出 int 范围。

输入样例：

4 4 10

输出样例：

4

算法

$$ \begin{align*} N &= a_0 + a_1k^1 + a_2k^2 + a_3k^3 + \cdots + a_nk^n, \\ \\ N’ &= a_0 + a_1 + \cdots + a_n, \\ \\ N - N’ &= a_1(k^1 - 1) + a_2(k^2 - 1) + a_3(k^3 - 1) + \cdots + a_n(k^n - 1). \end{align*} $$

我们知道：对任意的 $i\in Z$，均有$\left( k^i-1 \right) \%\left( k-1 \right) \equiv 0$，因此有

$$ root\left( N,k \right) =root\left( N\prime,k \right) \quad \text{其中}\left( N-N\prime \right) \%\left( k-1 \right) \equiv 0 \\ \\ root\left( N\prime,k \right) =root\left( N’‘,k \right) \quad \text{其中}\left( N\prime-N’‘ \right) \%\left( k-1 \right) \equiv 0 \\ \\ root\left( N’‘,k \right) =root\left( N’‘’,k \right) \quad \text{其中}\left( N’‘-N’‘’ \right) \%\left( k-1 \right) \equiv 0 \\ \\ \cdots \\ \\ root\left( N^{\left( m-1 \right)},k \right) =root\left( N^{\left( m \right)},k \right) \quad \text{其中}\left( N^{\left( m-1 \right)}-N^{\left( m \right)} \right) \%\left( k-1 \right) \equiv 0 $$

由于每次变换后，$N^{m+1}<N^{m}$ 且 $(N^{m+1}-N^{m})\%(k-1)\equiv0 $，所以经历若干次变化后最终
$$ root\left( N,k \right) =root\left( N\%\left( k-1 \right) ,k \right) $$
边界问题

如果 $N\%(k-1)==0$，那么正确答案是 $k-1$ 而不是 $0$

时间复杂度

$O(\log y)$

代码

#include <iostream>

using namespace std;

typedef long long LL;

int qmi(int a, int b, int p)
{
    int res = 1 % p;
    while(b)
    {
        if(b & 1)
            res = (LL) res * a % p;
        a = (LL) a * a % p;
        b >>= 1;
    }
    return res;
}

int main()
{
    int x, y, k;
    while(cin >> x >> y >> k)
    {
        int res = qmi(x, y, k - 1);
        if(res)
            cout << res << endl;
        else
            cout << k - 1 << endl;
    }
    return 0;
}