thesilione's blog

Hard POI Problem
By thesilione, 10 years ago, In English

Could someone give me a hint for this problem?

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

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

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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

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

      Would you explain more?

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

        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.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          I'm not sure if that always generates the smallest multiple.

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            Wow, really:( I didn`t see it:( But it's obvious anyway

            → Reply