求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)的值 (这里^为乘方，不是异或)，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

分析推导

1. 首先将 N用k进制表示 展开：

   N = a₀ + a₁ * k + a₂ * k² + ··· + a₀ * kⁿ

2. 则，N’ 表示如下：

   N’ = a₀ + a₁ + a₂ + ··· + a_n

3. 则 N - N’ 表示如下：

   N - N’ = a₁ * (k - 1) + a₂ * (k² - 1) + ··· + a_n * (kⁿ - 1)

4. 证明 (N - N’) % (k - 1) = 0

   由等比数列求和公式有: 1 + k + k² + ··· + k^{n - 1} = (1 - kⁿ) / (1 - k)

   ∴ kⁿ - 1 = (k - 1) * (1 + k + k² + ··· + k^{n - 1})

   ∴ (kⁿ - 1) % (k - 1) = 0

   又∵ N - N’ = a₁ * (k - 1) + a₂ * (k² - 1) + ··· + a_n * (kⁿ - 1)

   ∴ (N - N’) % (k - 1) = 0

5. 递推归纳

   令 N’ = N₁, N” = N₂, ···

   则有：

       (N - N₁) % (k - 1) = 0

       (N₁ - N₂) % (k - 1) = 0

       …

       (N_{r - 1} - N_r) % (k - 1) = 0

       其中 N_r 为我们要求的结果

   将上面的各个递推公式相加得到：

       (N - N_r) % (k - 1) = 0

   ∴ N_r = N % (k - 1)

6. 得出结论

   root(N, k) = N % (k - 1)

快速幂取模算法

点我查看

算法实现

此算法实现基于上面数学推得到的结论，以及快速幂取模算法

#include <iostream>

using namespace std;

long root(long x, long y, int k){
    long ans = 1;
    k -= 1;
    x %= k;
    while(y != 0){
        if(y & 1)
           ans = (ans * x) % k;
        y >>= 1;
        x = (x * x) %k;
    }
    return ans == 0 ? k : ans;
}

int main(){
    long x, y;
    int k;

    while(cin >> x >> y >> k)
        cout << root(x, y, k);
}