Уточнение (стандартное для задачи): разрезы — плоскости, параллельные граням тела, так что кубы имеют грани, параллельные граням параллелепипеда.
Пусть длины рёбер целого прямоугольного параллелепипеда равны $a,b,c\in {\mathbb{Z}}_{>0}$, а кубы одинакового целого ребра имеют сторону $s\in {\mathbb{Z}}_{>0}$.
Утверждение: такое разрезание возможно тогда и только тогда, когда $s$ делит каждое из чисел $a,b,c$, т.е. когда
$$s\mid a,s\mid b,s\mid c,$$ или эквивалентно $s\mid \gcd (a,b,c)$.
Доказательство.
1) Достаточность. Если $s\mid a,b,c$, то $a=s\alpha ,b=s\beta ,c=s\gamma$ для целых $\alpha ,\beta ,\gamma$. Тогда очевидно можно разбить параллелепипед на $\alpha \beta \gamma$ кубов размера $s$ (по равномерной сетке).
2) Необходимость. Рассмотрим одну грань параллелепипеда размером $a\times b$. Пересечение этой грани с кубами даёт покрытие прямоугольника одинаковыми квадратами со стороной $s$. Поскольку квадраты располагаются рёбрами параллельно сторонам прямоугольника и имеют целую сторону $s$, длина стороны $a$ разбивается на целое число отрезков длины $s$, значит $s\mid a$; аналогично $s\mid b$. То же рассуждение по второй оси даёт $s\mid c$. Таким образом $s$ делит все три размера.
Следствие: все допустимые целые стороны куба — это делители числа $\gcd (a,b,c)$. Число кубов в разрезании равно
$$N=\frac{a}{s}\cdot \frac{b}{s}\cdot \frac{c}{s}=\frac{abc}{s^3}.$$
Замечание: при другом понимании разрезания (например, с поворотами кубов или с нелинейными разрезами) формулировка и доказательство могут требовать уточнений; в классическом варианте, указанном выше, ответ — делимость размеров на сторону куба.