Блог пользователя techaddict

Can somebody explain the dp solution for the problem 152 Div2 B
Автор techaddict, 12 лет назад, По-английски

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

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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".

→ Ответить
  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

      → Ответить