Could someone give me a hint for this problem?

# | User | Rating |
---|---|---|

1 | tourist | 3947 |

2 | ecnerwala | 3654 |

3 | jiangly | 3627 |

4 | jqdai0815 | 3620 |

5 | orzdevinwang | 3612 |

6 | Benq | 3586 |

7 | Radewoosh | 3582 |

8 | Geothermal | 3569 |

8 | cnnfls_csy | 3569 |

10 | ksun48 | 3474 |

# | User | Contrib. |
---|---|---|

1 | awoo | 163 |

2 | maomao90 | 160 |

3 | adamant | 156 |

4 | atcoder_official | 155 |

5 | maroonrk | 152 |

6 | -is-this-fft- | 148 |

6 | cry | 148 |

6 | SecondThread | 148 |

9 | Petr | 147 |

10 | nor | 145 |

Could someone give me a hint for this problem?

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/08/2024 20:56:10 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

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 answerWould 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