Question

一个 $150\times324\times375$ 的长方体由 $1\times1\times1$ 的小正方体粘合而成。这个长方体的一条体对角线穿过多少个 $1\times1\times1$ 小正方体的内部？

A $150\times324\times375$ rectangular solid is made by gluing together $1\times1\times1$ cubes. An internal diagonal of this solid passes through the interiors of how many of the $1\times1\times1$ cubes?

答案

答案：768

知识点：长方体容斥原理最大公约数

难度评级：2270

小提示：

计算体对角线穿过各坐标网格平面的次数

Count the coordinate-plane crossings of the space diagonal

大提示：

用最大公约数修正同时穿过两个或三个网格平面的情形

Correct for crossings of two or three grid planes at once using greatest common divisors

解答：

对于一个 $a\times b\times c$ 的方块阵列，对角线分别穿过三个方向上的 $a-1$ 、 $b-1$ 和 $c-1$ 个内部网格平面。两个方向的穿越分别有 $\gcd(a,b)-1$ 、 $\gcd(a,c)-1$ 和 $\gcd(b,c)-1$ 次重合，而三个方向的穿越有 $\gcd(a,b,c)-1$ 次重合。加上起始小正方体，再使用容斥原理，得到 $\begin{gathered}a+b+c-\gcd(a,b)\\-\gcd(a,c)-\gcd(b,c)\\+\gcd(a,b,c)\end{gathered}\text{。}$ 三个两两最大公约数分别为 $6$ 、 $75$ 和 $3$ ，三者的最大公约数为 $3$ 。因此对角线穿过内部的小正方体个数为 $\begin{gathered}150+324+375\\-6-75-3+3=768\end{gathered}\text{。}$

For an $a\times b\times c$ array, the diagonal crosses $a-1,$ $b-1,$ and $c-1$ internal grid planes of the three orientations. Crossings of two orientations coincide $\gcd(a,b)-1,$ $\gcd(a,c)-1,$ and $\gcd(b,c)-1$ times, and triple crossings occur $\gcd(a,b,c)-1$ times. Adding one for the initial cube and applying inclusion-exclusion gives $\begin{gathered}a+b+c-\gcd(a,b)\\-\gcd(a,c)-\gcd(b,c)\\+\gcd(a,b,c).\end{gathered}$ Here the pairwise gcds are $6,$ $75,$ and $3,$ and the triple gcd is $3.$ Thus the number of cube interiors met is $\begin{gathered}150+324+375\\-6-75-3+3=768.\end{gathered}$

1996 AIME 第 14 题

答案：768

难度评级：2270

小提示：

大提示：

解答：

其他年份的第 14 题