strange14's blog

How to Solve this DP problem?
By strange14, history, 5 years ago, In English

1559E - Mocha and Stars

Tutorial uses mobius function to solve this problem. How can we solve this using DP, as I have seen many people use it in their solutions.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
5 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

Let $$$dp[i]$$$ be the number of ways with $$$\gcd = i$$$.

If you calculate it in descending order of $$$i$$$, $$$dp[i] =$$$ (number of ways with values multiples of $$$i$$$) — $$$\sum_{k=2}^{\lfloor m/i \rfloor} dp[ik]$$$.

You can check out similar techniques in this blog.

→ Reply