thesilione's blog

Hard POI Problem
By thesilione, 13 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

»
13 years ago, hide # |
 
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
»
13 years ago, hide # |
← 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
  • »
    »
    13 years ago, hide # ^ |
    ← 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
    • »
      »
      »
      13 years ago, hide # ^ |
       
      Vote: I like it +3 Vote: I do not like it

      Would you explain more?

      → Reply
      • »
        »
        »
        »
        13 years ago, hide # ^ |
         
        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