#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;


int bfs(int num){
	queue<int> q;
	q.push(num);
	if(num%n==0&&num>=n) return num;
	
	while(!q.empty()){
		int cur = q.front();
		q.pop();
		if(cur%n==0&&cur>=n) return cur;
		for(int i=0;i<=1;i++){
			int nx = cur*10+i;
			q.push(nx);
		}
	}
	
}



int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

	cin>>n;
	cout<<bfs(0);

    return 0;
}

同余定理真是乱入 大家有时间学学 + - * / 余数的处理 当入门小数论了 /注意点就行

#include<bits/stdc++.h>
using namespace std;
#define int long long
/* 简单介绍一下题意：对于一个数n 找它的一个非0倍数 m 
   要求：1：m由0/1组成 2：m一定存在多解 输出最短长度 
  简单分析：1这个m要最短长度----BFS
            2我们是在以位数的角度在增加长度-但如果长度到100 int 一定一定爆了
  对于2：我们分析
   1：明确目标 找第一个m 使得m%n==0
   2；分析：	
     10%3=1   100%3=1--本质 (10%3)*10%3==1*10%3
     a%b==r   (a*10+d)%b== (a%b*10+d)%b===(r*10+d)%b  
   3: 如何存储？答：对于每个余数我们可以 str[r]=string----更新：str[nr]=str[r]+d;
   最终：输出str[0]
   3:注意：如果 a=xxx b=xxxxxx 他俩余数都是r我们存谁 存a 才能保证最短
          所有：在存的时候保证没有被存过（放在长的覆盖） 
   4:初始入口 1	   	  	  
*/
const int N=250;
unordered_map<int,string> ump;//余数---string 
int n;
int m;
signed main()
{ std::ios::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);
  	 cin>>n;
  	 queue<int> q;
  	 int b=1%n;
  	 ump[b]="1"; 
  	 q.push(b);//起点
	 while(q.size())
	 { 
	   auto r=q.front();//旧的余数 
	   q.pop();
	   if(r==0) break;//找到目标 
	   for(int i=0;i<=1;i++)
	   {
	   	 int nr=(r*10+i)%n;//新余数 
	   	 char j=i+'0';
	   	 if(!ump.count(nr))
		{	 
		 ump[nr]=ump[r]+j;
		 q.push(nr); 
	    }
	   } 	
	 }   
	cout<<ump[0]<<"\n";
	return 0;
}

n = int(input())
q = [[] for _ in range(10)]
for i in range(10):
    q[i*n%10].append(i)
from collections import deque
d = deque([(0, 0, 0)])
while d:
    x, l, r = d.popleft()
    p = 10 ** l
    res = x * p + r
    if not x and res:
        break
    l+=1
    for y in q[-x % 10]:
        d.append(((x + y * n) // 10, l, r))
    for y in q[(-x+1) % 10]:
        d.append(((x + y * n) // 10, l, r + p))
print(res)

#include<bits/stdc++.h>
using namespace std;

const int N = 210;
int n;
deque<pair<int,string>> q;

/*
	解释为什么代码只维护余数。
	设：
		原数 = A
		A 对 n 的余数 = r
		后面加一个数字 d（0 或 1）
		
	所以：新数%n = (A*10 + d)%n
				 = [(A*10)%n + d%n]%n   ->同余定理
				 = [(A%n * 10%n)%n + d%n]%n
		         = [(r%n * 10%n)%n + d%n]%n    因为A%n=r，可以直接进行替换，又因为 0<= r < n ,所以 用 r%n 并不会影响整个式子的值	
				 = [(r*10)%n + d%n]%n    再用同余定理把它换回去
				 = [r*10 + d]%n
*/


string bfs() {
	q.push_back({1,"1"});
	
	while(!q.empty()) {
		auto x = q.front();
		q.pop_front();
		
		// 当末尾加 0 时
		int a = (x.first*10)%n;      
		string sa = x.second + "0";
		if(a==0) {
			return sa;
		}
		q.push_back({a,sa});   // 队列只维护余数
		
		// 当末尾加 1 时。
		int b = (x.first*10 + 1)%n;
		string sb = x.second + "1";
		if(b==0) {
			return sb;
		}
		q.push_back({b,sb});
	}
	return "";  
}

void solve() {
	cin >> n;
	if(1%n==0) {   // 特判一下，如果n取1，直接输出结果
		cout << 1 << endl;
		return;
	}
	string ans = bfs();
	cout << ans << endl;
	
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int t = 1;
	// cin >> t;
	while(t--) {
		solve();
	}
	return 0;
}