### thesilione's blog

By thesilione, 10 years ago,

Could someone give me a hint for this problem?

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

• +5

 » 10 years ago, # |   0 In this problem we must use bfs on a graph, where each vertex is the remainder of the division by n.
 » 10 years ago, # | ← Rev. 2 →   0 Why do you minusing it? Can't solve? That's nice problem
•  » » 10 years ago, # ^ | ← 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 years ago, # ^ |   +3 Would you explain more?
•  » » » » 10 years ago, # ^ |   +3 Check out Euler Function and Eulers 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. Its 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.
•  » » » » » 10 years ago, # ^ | ← Rev. 2 →   0 I'm not sure if that always generates the smallest multiple.
•  » » » » » » 10 years ago, # ^ | ← Rev. 2 →   0 Wow, really:( I didn`t see it:( But it's obvious anyway