Количество разложений числа на множители N<=2*10^9

В первую очередь надо разложить число на простые множители. Время за O(sqrt(N))
И получится что-то вот такое:

p1^a1 * p2^a2 * ... pk^ak, где pi - это i-тое простое число
Ответом будет (a1+1)*(a2+1)*...(ak+1)

Например, если N=100, то 100 = 2^2 * 5^2, и ответ = (2+1)*(2+1) = 3*3 = 9.
Вот и все
Можете http://acmp.ru/index.asp?main=solution&id_task=171 посмотреть

Ну с динамикой не всё хорошо по асимптотике, хотя есть подозрение, что всё же она должна укладываться в TL.

Дело в том, что динамика - фактически идёт по делителям заданного числа N, а т.к. N<=10^9, то по известной оценке число делителей будет в худшем случае в районе 1000.

Динамика видится такой: d[ i ][ j ] - количество разбиений числа i на множители, если разрешается брать только множители >=j. Без второго параметра не получается добиться того, чтобы 2*3 и 3*2 считались разными.
А переходы в динамике: мы перебираем число k как делитель i, больше либо равный j, и прибавляем к d[ i ][ j ] число d[i/k][k].

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

P.S. На самом деле, такое ощущение, что эту динамику можно сделать и за квадрат...