一点一点前进...

0%

欧拉项目 | 348题 | 一个平方数和一个立方数之和是回文数

发表于 分类于 ， Disqus：

Problem 348

很多数能够写成一个平方数和一个立方数之和的形式，其中一些可能会有多种组合形式。
有一些数有4种组合形式，且它是一个回文数。比如5229225是一个回文数，能写成四种组合形式：

1
2
3
4
2285^2 + 20^3
2223^2 + 66^3
1810^2 + 125^3
1197^2 + 156^3

找到前五小的这种数，求和。

一个数是否能拆解成一个平方数和一个立方数之和是比较难的问题，但是构造一个这样的数就比较简单了。我开始假设在int范围内就至少有五个满足题意的数。
下面这段代码就会找出所有是一个平方数和一个立方数之和的回文数，并且统计了它们出现的次数。

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
var counts = new Dictionary<int, int>();
for (int i = 2; i < Math.Sqrt(int.MaxValue); i++)
{
    for (int j = 2; j < 1291; j++)
    {
        long sum = i * i + j * j * j;
        if (sum > int.MaxValue)
        {
            break;
        }

        int s = (int)sum;
        if (Utils.IsPalindrome(s.ToString()))
        {
            if (counts.ContainsKey(s))
            {
                counts[s]++;
            }
            else
            {
                counts[s] = 1;
            }
        }
    }
}

然后找出出现次数为4的回文数，排序，取前五，求和。

1
2
3
4
var candidates = counts.Where(pair => pair.Value == 4).Select(pair => pair.Key).ToList();
candidates.Sort();

return candidates.Take(5).Sum();