Олимпиадная задача по математике Прямоугольный параллелепипед состоит из a*b*c правильных кубиков. Сколько всего кубиков пронзает диагональ такого прямоугольника?
По аналогии с двухмерным случаем мне кажется, ответ должен быть a + b + c - [ НОД(a,b)+НОД(b,c)+НОД(a,c) ]. К сожалению, 1 кубик похоже теряется, потому что правильные ответы включают в себя число на 1 большую, чем по этой формуле.
Почему теряется только 1, а не 2? Например, при прямоугольнике 35 × 40 × 56 правильный ответ 112

Предыдущий
вопрос Следующий
вопрос

Когда вы находите общий делитель для двух измерений (к примеру НОД(a,b)), эти кубики будут пронзаны диагональю дважды. Поэтому, чтобы избежать подсчета лишних кубиков, необходимо вычесть один из общих делителей.

Таким образом, правильная формула для определения количества кубиков, которые пронзает диагональ прямоугольного параллелепипеда, будет:

a + b + c - (НОД(a, b) + НОД(b, c) + НОД(a, c)) - 1

С учетом этой поправки, вы сможете получить правильный результат для любого прямоугольного параллелепипеда, построенного из правильных кубиков.