Problem:A $150\times 324\times 375$ rectangular solid is made by gluing together $1\times 1\times 1$ cubes. An internal diagonal of this solid passes through the interiors of how many of the $1\times 1\times 1$ cubes?
I tried it and I had no clue of approaching. Then I saw solution on AOPS but didn't find it satisfactory. The solution went like this
$150+324+375- gcd(150,324)-gcd(150,375)-gcd(324,375)+gcd(150,324,375)= 768$.
Link is artofproblemsolving.com/community/c4h46950p315374
I think they have used PIE but I don't know how it solved the problem. Anybody can explain me??
Consider this cuboid on a graph.
Now mark planes, for each dimension in the following way.
$$x=1,x=2,...,x=150$$ $$y=1,y=2,...,y=324$$ $$z=1,z=2,...,z=375$$
Now the internal diagonal passes through all such planes.
Now it is equivalent to count intersections of the diagonal with the planes, which can be easily counted with the inclusion-exclusion principle.
For clarity: Now the part that why is it $\gcd(a,b)$: Consider starting from $(0,0,0)$. Imagine the internal diagonal as a vector. This vector has direction vector $(150,324,375)$. When you move in the direction of the positive $x$ axis, you also move $324/150$ units in the $y$ direction and similarly $375/150$ in the $z$ direction. When for example, $x$ and $y$ will be integers? Can you relate $\gcd(x,y)$ to this?