Could someone give me a hint for this problem?
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | Um_nik | 3396 |
# | User | Contrib. |
---|---|---|
1 | Um_nik | 163 |
2 | cry | 161 |
3 | maomao90 | 160 |
4 | -is-this-fft- | 159 |
5 | atcoder_official | 158 |
5 | awoo | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | maroonrk | 152 |
10 | Dominater069 | 149 |
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