On Timus getting wa on test 2 ..somebody plz tell me what is wrong?
the problem 1049 brave ballon
my code: ideone
Idea : what i tried to do was ..calculate all prime factors of those 10 num;
Then maintained dp where dp[x]..would be n^(x or higher)...the number of factor which has x or higher power.. then i calculate the number of situation where all numbers are prime, i gradually lessened the length and calculate new numbers where the situation was of that length;
if it was : 36 length 4: 2, 3 case [2*2*3*3] length 3 : 4,9,6 cases[ 4 * 3* 3, 2*2*9, 6*6] length 2 : 12, 18 cases [12*3, 18*2]
length 1 : 1, 36
in my code length was denoted as x
In Line — 37 You are modifying n {n = n/i}, and using sqrt(n) in the for loop condition(line 35)
Hmm, I am not certain I understand your DP idea. Could you explain more precisely what your dp[x] is meant for and how(and why) do you use it to calculate the final answer.
Alternatively, this problem has a rather simple number theory solution, which I would be happy to explain to you (either here or message you directly).
thanks for the reply man... sorry for the delay.. i figured it out.....i figured the number theory solution too..... i think it is (power of prime factor1+1)*(power of factor2+1)*......... what i tried to do was: what if I multiply x numbers from total factors how many new factor would i get. it was foolish idea i tried to from a new number one at a time instead of thinking the combination approach.