Could someone give me a hint for this problem?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | adamant | 157 |
6 | awoo | 157 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | djm03178 | 153 |
Could someone give me a hint for this problem?
Name |
---|
In this problem we must use bfs on a graph, where each vertex is the remainder of the division by n.
Why do you minusing it? Can't solve? That's nice problem
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
Would you explain more?
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.
I'm not sure if that always generates the smallest multiple.
Wow, really:( I didn`t see it:( But it's obvious anyway