Problem Link: http://codeforces.com/gym/101875/problem/C
Hi,
I was recently trying the aforementioned question. My idea was: I can find all primes up to 1e6, after that I can do the prime decomposition of each of the v[i] and find the overall prime decomposition of a, in the form p_1^x_1 * p_2^x_2 .. p_n^x_n.
But after this, I'm stuck with how to find the number of divisors of a number (from its prime decomposition) that have exactly b divisors.
Any help would be highly appreciated!
Hint:
The number of divisors of a number with prime factorization p1a1p2a2p3a3....
is equal to (a1 + 1)(a2 + 1)(a3 + 1)....
Solution:
Let dp[i][j] be the number of ways to get a number with j divisors from the first i prime factors of the big number.
When you set the current prime factor's power to x, you multiply the number of divisors by (x + 1), So you move to state (i + 1, j * (x + 1))
Got it, thank you! Never realized I could use the fact that B was bounded by 10^3.