一点一点前进...

0%

欧拉项目 | 119题 | 某数各数字之和的若干次幂等于该数本

发表于 分类于 ， Disqus：

Problem 119

512是一个很有意思的数字，5+1+2=8，8^3=512
614656 = 28^4
an是满足这些条件的数列：
至少有两位数
各个数字之和的若干次幂等于该数
求a30

对于这种题目，欧拉项目有个套路，你不太可能遍历每个数字去检查它是否满足条件的时候，就要换种思路，快速构造满足题目的集合，然后按照题目找到答案。
回到这个题目，我个人感觉a30不会超过long能表示的范围，所以我只要看long以内的就可以了。
第一步，找到数字之和s的范围。最小值是2，因为至少有两位数；最大值是9*19，因为long.MaxValue有19位数字。其实这个范围比实际范围大一些，但是无所谓了，多的不多，不会影响程序效率。
第二步，求s的若干次幂，从2次幂开始，3次幂，4次幂等等，直到超出long的范围。这些都是可能的值n。满足这一步的n不到1700个。
第三步，求n的各个数字之和sum，如果sum等于s，那么这个n就是满足题意的。
第四步，把所有的n排序，找出第三十个即可。很幸运，long以内有34个满足题目的数。

下面是代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
var candidates = new List<long>();
for (int i = 2; i < 9 * long.MaxValue.ToString().Length; i++)
{
    int power = 2;
    while (true)
    {
        var ret = BigInteger.Pow(i, power);
        if (ret > long.MaxValue)
        {
            break;
        }

        long number = (long)ret;
        long candidate = number;

        long sum = 0;
        while (number != 0)
        {
            sum += number % 10;
            number /= 10;
        }

        if (sum == i)
        {
            candidates.Add(candidate);
        }

        power++;
    }
}

candidates.Sort();

return candidates[29];