15. 求 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)的值

示例1

输入

4 4 10

输出

4

思路一： 找规律

刚做完一道简单题很开心，来了这道题又不会做，不能直接按题意写出代码，会超过数字类型长度，需要观察出规律来做，参考了网上的方法。
对于 root(N, k)，如果 N 不小于 k，那么则把 N 的 k 进制表示的各位数字之和赋给 N，记为 N^'，继续求 root(N^', k)，N 可以表示为多项式 a₀ + a₁k + a₂k² + ... + a_nkⁿ，N^' 则为 N 的多项式系数和，即 a₀ + a₁ + a₂ + ... + a_n，观察到如果 N = (a₀ + a₁k + a₂k² + ... + a_nkⁿ)²，那么 N^' = (a₀ + a₁ + a₂ + ... + a_n)²，因为这个系数的和整体运算和拆开运算结果一样，根据这一规律，对于 root(x, y, k)，可以写出：
（1）y 是偶数，root(x, y, k) = root(root(x, y / 2, k) * root(x, y / 2, k), 1, k)
（2）y 是奇数，root(x, y, k) = root(root(x, y / 2, k) * root(x, y / 2, k) * root(x, 1, k), 1, k)

解法一

#include<stdio.h>

long root(long x, long y, long k) {
    if (y == 1) {    //次方为 1 时，才开始处理，不然转化到次方为 1 为止，有人可能有一个疑惑，如果次方大于 1 时，x^y < k 呢，那么不输出 x^y 而是继续把 y 降次到 1 会影响结果吗，不会，因为 k > 1,所以 x^y < k 时 x 肯定小于 k ,这种情况降次之后还是会输出 x^y
        if (x < k)
            return x;
        else {
            while (x >= k) {    //持续做进制处理
                long sum = 0;
                while (x > 0) {
                    sum += x % k;
                    x /= k;
                }
                x = sum;
            }
            return x;
        }
    }
    else {
        if (y & 1)    //y 为奇数的情况
            return root(root(x, y / 2, k) * root(x, y / 2, k) * root(x, 1, k), 1, k);
        else
            return root(root(x, y / 2, k) * root(x, y / 2, k), 1, k);
    } 
}

int main() {
    for(long x, y, k; ~scanf("%ld %ld %ld", &x, &y, &k);)    //今天刚看到的一种控制多组输入的方法，长见识了
        printf("%ld", root(x, y, k));
    return 0;
}

思路二： 经典算法之快速幂取模