Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Gilgamesh_01's blog

By Gilgamesh_01, history, 10 months ago, In English,

Hi everyone, I need help with this problem, I tried 3 days, but nothing work. The problem consists about find the x smallest múltiple of a number n, and x only consists of 0 and 1 for example n=2,x=10 and n=3,x=111.. please help I try brute force but it doesn't work

 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Gilgamesh_01 (previous revision, new revision, compare).

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Constraints on n?

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe bfs works? Make $$$n$$$ points, denoting the remainder when $$$x$$$ modulo $$$n$$$ is $$$i$$$. We start bfs from 1, and find the shortest path to 0.

At the same time, note that when extending points, first add the point when using 0, then using 1.

(Inspired from 1209F)