Можно. Например выводить мало больших строк, а не много маленьких, объединяя строки через символ перевода строки, выводить с помощью gets  puts, а не cout или чего-то еще если на С++.

Вот ещё моё решение. На самом деле, если очень глубоко покопаться, оно совпадает с Пашиным, просто я расписал покороче ту же формулу (которая, кстати, следует из леммы Бёрнсайда, групповая структура налицо).

Как можно было рассуждать.

Разобъём все разбиения (каламбур!) на классы эквивалентности относительно циклического сдвига.

Рассмотрим главный период A в разбиении. Понятно, что A | k. Также понятно, что размер класса эквивалентности для этого разбиения сопадает с A.

Пусть F(A) - количество разбиений с главным периодом A. Тем самым получаем, что ответ X = sum(F(A), A=1..k) = sum(F(A), A | k), т.е. F(A) при A не делящем k есть ноль.

Пусть G(a, b) есть количество разбиений числа a на b положительных целых слагаемых. Известным образом оно равно биномиальному коэффициенту C(a + b - 1, b - 1).

Выведем рекуррентную формулу для F(A). Заметим, что любое разбиение с главным периодом A однозначно задаётся своими первыми A числами, которые в сумме должны давать n / A (тем самым, F(A) при A не делящем n тоже равно нулю). Значит, F(A) = G(n / (k / A), A) - sum(F(B), B | A), т. к. мы посчитаем также все разбиений с кратным периодом.

Теперь про асимптотику. Можно рассматривать только делители, например, n, которых не больше тысячи. Получаем решение за O(d(n)^2), где d(n) есть количество делителей числа n.