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

Hard POI Problem
Автор thesilione, 10 лет назад, По-английски

Could someone give me a hint for this problem?

http://main.edu.pl/en/archive/oi/2/jez

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

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

In this problem we must use bfs on a graph, where each vertex is the remainder of the division by n.

→ Ответить
»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Why do you minusing it? Can't solve? That's nice problem

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

    Oh, i thought that there is some condition like length of answer must be less than 1000. Of course, this problem is obvious: number 1111111....1111000000...000, with 9φ(n) of "1" and 30 "0" is an answer

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

      Would you explain more?

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

        Check out Euler Function and Euler`s theorem.

        We can reduce our problem to n so that gcd(n, 2) = gcd(n, 5) = 1. Now, we know that 10φ(n) - 1 is divisible on n, i.e. 99999...999 with φ(n) "9" is divisible on n. It`s easy to check that 1111111....1111000000...000, with 9φ(n) of "1" and 30 "0" is divisible on 10φ(n) - 1 so we are done.

        → Ответить