一点一点前进...

0%

欧拉项目 | 86题 | 立方体路线

发表于 分类于 ， Disqus：

Problem 86

小蚂蚁从立方体的一点走最短距离爬到对顶点，爬过的长度可能是整数，比如立方体三维分别是6，5，3，那么最短距离是10，但也不总是整数。
对于三边最长是$M\times M\times M$的立方体，当$M=100$时，有2060个边长均为整数的不一样的立方体，其蚂蚁爬过的最短距离是整数，而$M=99$时，有1975个不同的立方体。
求立方体个数超过一百万时$M$的最小值。

其实这个题目不难，关键点在于不需要计算出具体满足题意的值，只需要计数即可。
不妨设$M=a\geq b\geq c$，那么$2\leq b+c\leq 2a$，斜边长是$\sqrt{a^a+(b+c)^2}$，如果斜边长是整数，那么$b$和$c$可以在一定范围内变化。$b$最小也就是$b+c$的一半或者一半加一，最长的话就是等于$a$，同时要满足$c\geq 1$。所以很容易通过某个给定的$a$来得到满足条件的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int GetCountByA(int a)
{
    int count = 0;
    for (int bc = 2; bc <= 2 * a; bc++)
    {
        int slope = (int)Math.Sqrt(a * a + bc * bc);
        if (a * a + bc * bc == slope * slope)
        {
            int bStart = bc % 2 == 0 ? bc / 2 : bc / 2 + 1;
            int bEnd = Math.Min(a, bc - 1);
            count += bEnd - bStart + 1;
        }
    }
    return count;
}

对$a$，也就是$M$进行遍历，当总数大于一百万时停止，得到要求的$M$。

1
2
3
4
5
6
7
int count = 0;
int a = 2;
while (count < 1_000_000)
{
    a++;
    count += GetCountByA(a);
}