techaddict's blog

Can somebody explain the dp solution for the problem 152 Div2 B
By techaddict, 12 years ago, In English

problem link [http://www.codeforces.com/contest/248/problem/B]

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

»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The least common multiple of this numbers (2,3,5,7) is 210. So you are asked to find smallest n-digit number, which is divisible by 210.

Let's take smallest n-digit number X=(10^(n-1)). We can consider all numbers from X to X+210 and choose the one, which is divisible* by 210. Of course that one will be the answer.

*Since X is very large (maximum 10^5 digits), you've got to use "long integer arithmetics".

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Thanks a lot. My solution in python runned out of time using same approach.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Hers is O(n) solution:

      Let dp[i] be the remainder of 10^i when divided by 210. dp[0]=1; dp[i+1]=(dp[i]*10)mod 210;

      We can precalculate dp[0...10^5] in O(10^5) time.

      Let's take smallest n-digit number (10^(n-1)). It gives dp[n-1] as a remainder when divided by 210. Therefore (10^(n-1))-dp[n-1]+210 is divisible by 210.

      So, 10^(n-1)-dp[n-1]+210 is the answer.

      The answer will be a number of following type :

      • First digit will be equal to 1.

      • The number obtained by last three digits together should be equal to 210-dp[n-1].

      • all other digits will be equal to 0.

      → Reply