I've been trying this problem on spoj but not been able to come up with a optimal solution. The statement translates to — find number of ways to divide a number 'm' into 'n' distinct positive numbers.

1<=m,n<=10^6 also, m*n<=10^6

I was thinking of applying dp, but was stuck at it because it required all the numbers to be distinct. It is obvious that for all values of 'n' around 1400 and above, answer is 0.But that didn't help me in my approach.

Can dp be applied? Or could it be solved using other method?

EDIT: Solved using dp — consider a list of numbers — 1,2,3,....n (minimum possible) and at each index i,increment all numbers (i to n) by some constant.Apply dp here. I still faced some time complexity issues — http://ideone.com/yXCYeo I had to optimise it using sieve — http://ideone.com/jpHIlR

Please let me know if you used some other method.