SPOJ PROBLEM EIDSALAMI2
Difference between en1 and en2, changed 375 character(s)
I've been trying this [problem](http://www.spoj.com/problems/EIDSALAMI2/) 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 &mdash; consider a list of numbers &mdash; 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 &mdash; http://ideone.com/yXCYeo↵
I had to optimise it using sieve &mdash; http://ideone.com/jpHIlR↵

Please let me know if you used some other method.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English prrateekk 2016-08-18 00:30:46 375
en1 English prrateekk 2016-08-17 22:46:55 596 Initial revision (published)