求root(N, k)【數學、快速冪、c++】

题目描述

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)的值

分析

閱讀完題面，筆者立即用c++寫下了root(N, k)函數

long long root(long long n, int k) {
    if (n < k) return n;
    long long np = 0;
    while (n) {
        np += n % k;
        n /= k;
    }
    return root(np, k);
}

顯然，這是一個遞歸的函數。根據題目描述，n和k都是正整數，且 $0<root(n, k)<k$ .
root函數的定義是很簡單的。難點在於， $n=x^y$ 的取值範圍可能超過32位int類型所能表示的範圍。

能否在計算機上儲存n呢

遇到數據大小超過數據類型所能表示的範圍這種問題時，很容易想到是否能用更大的類型，或者自定義類型來表示該數據？不能用32位來表示，那能否使用64位來表示呢？64位不行，128位又如何呢？1000位又如何呢？
答案是都不行。由題可知， $n$ 的最大值為 $2000000000^{2000000000}$ 。
估算，是工程師的一項重要能力。《編程珠璣》中曾表述過類似的觀點。對於此題，不妨先估算一下用多少位的整型可以表示n。眾所周知， $2^{10}=1024$ ，於是 $2000000000\approx 2^{31}$ ，於是 $2000000000^{2000000000}\approx 2^{62000000000}$ 。要表示後面這個數，需要 $62000000001$ 位才行。
總而言之，要想用整形來表示 $n$ ，簡直是不可能的。於是，我們必須在不知道n的具體值的情況下求得答案。

能否依次計算出n在各個位上的數值呢

一計不成，再生一計。回顧題目，題中說道“N'为N的k进制表示的各位数字之和”。似乎是在暗示，N的值不重要，只要依次計算出N各個位上的數，得到他們的總合就可以了。這個思路是否可行呢？
不妨設k=2. 那麼n便有數十億位。即使能依次求得N的各個位，將各個位的數字相加需要數十億次循環，這個代價仍是不可接受的。

root函數本身的規律

n的數值是無法儲存的，而且不能去求它各個位上的數，因為它的位數太多了。這些都是無法跨越的障礙。從應試的角度看，障礙是存在的，但路是一定存在的，只不過它可能是曲折的。
回顧學習算法的過程中，學到的那些思想：遞歸、分治……將大的問題分解成小的問題的思想。
在這個問題中，能否將大問題分解成小問題？換句話說，root函數是否具備這樣的性質？
進一步猜測到， $root(ab, k)$ 和 $root(a, k)$ ， $root(b, k)$ 之間具有怎樣的聯繫？
不妨設 $k = 10, a = b = 11$ .
$root(11\times11, 10) = root(121 ,10) = 4$
$root(11, 10) = 2$
$\vdots$
總之，經過嘗試和觀察，筆者福至心靈，發現了（猜到了）這樣的規律
$root(ab, k)=root(root(a, k)root(b, k), k)$
哈哈。想到這點的時候，筆者心甘情願地從冬日的被窩里爬了出來，刷刷寫出了如下代碼

#include <stdio.h>

long long root(long long n, int k) {
    if (n < k) return n;
    long long np = 0;
    while (n) {
        np += n % k;
        n /= k;
    }
    return root(np, k);
}

int root2(int x, int y, int k) {
    if (y == 0) return root(1, k);
    if (y == 1) return root(x, k);
    int r1 = root2(x, y / 2, k);
    int r2 = root2(x, y % 2, k);
    return root(r1 * r1 * r2, k);
}

int main() {
    int x, y, k;
    while (scanf("%d%d%d", &x, &y, &k) != EOF) {
        int res = root2(x, y, k);
        printf("%d\n", res);
    }
    return 0;
}

程序員最開心的事，莫過於代碼一次性通過了。
代碼用到快速冪和進制轉化的知識。

其它方法

通過此題後，筆者快樂的心情也漸漸平淡下來。畢竟自己只不過是猜中了一個公式而已，並不是什麼值得誇耀的事。
看看大佬們是如何作答的吧。
參考原文，筆者將其思路整理并記錄于下：
$N=a_0+a_1 k+a_2 k^2 + a_3 k^3 + \cdots$
$N'=a_0 + a_1 + a_2 + \cdots$
兩式想減，得
$N-N'=a_1(k - 1)+a_2(k^2-1)+a_3(k^3-1)+\cdots$
於是
$(N-N') \mod (k-1) =0$
類似的
$(N'-N'') \mod (k-1)=0$
$\vdots$
$(N^r-{N^r}')\mod(k-1)=0$
以上式子相加，得
$(N-Nr')\mod(k-1)=0$
其中 $0<{N^r}'<k$ . 於是
$root(N, k) = {N^r}'=\begin{equation} \left\{ \begin{array}{rcl} N\mod(k-1)& & k-1不能整除N\\ k-1& & k-1正好整除N\\ \end{array} \right. \end{equation}$ .