Bonus Money Problem in Hacker's Earth?

Revision en1, by mohamedeltair, 2018-09-18 08:10:40

Here is the link of the problem: Bonus Money

My question is about sub-task 3. It is mentioned in the editorial of the problem that dp[n][r+xg] is a polynomial P(x) where g=lcm(1, 2, 3, ..., n) and 0 <= r < g. What is the general proof of this? And what is the significance of lcm(1, 2, 3, ..., n) that made the expression polynomial? (That is, it is said specifically that dp[n][r+xg] is a polynomial and not just dp[n][x]). I have referred to the comments on the editorial looking for a proof, but I have just found a small proof for only dp[1][x], dp[2][2x], dp[2][2x+1], dp[3][6x]. And not a general proof which generalizes to any n.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English mohamedeltair 2018-09-18 08:10:40 761 Initial revision (published)