021. How Many Voxels Does the Ray Pass Through?

Let a cube with side length 1 be called a voxel. Given natural numbers $l$, $m$, $n$, stack $lmn$ voxels to form a rectangular parallelepiped with side lengths $l$, $m$, and $n$ respectively. Determine the number of voxels through which one diagonal of this rectangular parallelepiped passes internally.

---

The positions of $lmn$ voxels can be represented using coordinates as follows. $$\begin{aligned} (x, y, z) \qquad 1 \leq x \leq l, \quad 1 \leq y \leq m, \quad 1 \leq z \leq n \end{aligned}$$

This is represented by the highest number among the coordinates of the eight vertices of a single voxel. Now, when the diagonal is defined as the ray moving from the origin $(0, 0, 0)$ to the point $(l, m, n)$, the total coordinate change is $l + m + n$.

• The ray passes through a voxel’s face (excluding the boundary lines)
  • When moving to the next voxel, only one of the $(x, y, z)$ coordinates increases by 1.
• The ray passes through a voxel’s edge (excluding vertices)
  • When moving to the next voxel, only two of the $(x, y, z)$ coordinates increase by 1.
• The ray passes through a voxel’s vertex
  • When moving to the next voxel, all of the $(x, y, z)$ coordinates increase by 1.

That is, $l + m + n$ can be viewed as a value calculated assuming the ray only passed through the faces of voxels. Therefore, this value must be adjusted to obtain the actual number of voxels traversed. When $gcd()$ is defined as the function representing the greatest common divisor, the following can be determined.

• The ray passes through $gcd(m, n)$ edges parallel to the $x$-axis.
• The ray passes through $gcd(l, n)$ edges parallel to the $y$-axis.
• The ray passes through $gcd(l, m)$ edges parallel to the $z$-axis.

$l + m + n$ assumes the ray traverses only faces, but when it actually crosses edges, two coordinate changes occur in a single movement. Therefore, the number of edges traversed by the ray must be subtracted. Additionally, cases where the ray passes through a vertex, causing all three coordinates to change, must be included. However, since this subtraction causes such cases to be deducted redundantly, $gcd(l, m, n)$ must be added back. Therefore, the number of voxels traversed by this ray is as follows. $$\begin{aligned} l + m + n - gcd(l, m) - gcd(m, n) - gcd(l, n) + gcd(l, m, n) \end{aligned}$$