fork download
copy 
  1.  
  2.  
  3.     #include <bits/stdc++.h>
  4.     using namespace std;
  5.  
  6.     #define pii pair<int,int>
  7.     #define pip pair<int,pii>
  8.     #define pb push_back
  9.     #define mp make_pair
  10.     #define ff first
  11.     #define ss second
  12.     #define MOD 1000000007
  13.  
  14.     typedef long long ll;
  15.     //int dx[]={1,-1,0,0};
  16.     //int dy[]={0,0,1,-1};
  17.  
  18.     struct node
  19.     {
  20.         string s;
  21.         int mod;
  22.     };
  23.  
  24.     int visited[20000+10];
  25.  
  26.     void bfs(int num)
  27.     {
  28.         queue<node> q;
  29.         node temp,hold,poss1,poss2;
  30.  
  31.         temp.s="1";
  32.         temp.mod=atoi(temp.s.c_str())%num;
  33.         if(temp.mod==0)
  34.         {
  35.             cout<<num<<endl;
  36.             return;
  37.         }
  38.         q.push(temp);
  39.         visited[temp.mod]=1;
  40.         while(!q.empty())
  41.         {
  42.             hold=q.front();
  43.             q.pop();
  44.  
  45.             if(hold.mod==0)
  46.             {
  47.                 cout<<hold.s<<endl;
  48.                 break;
  49.             }
  50.  
  51.             poss1.s=hold.s;
  52.             poss1.s+='0';
  53.             poss1.mod=atoi(poss1.s.c_str())%num;
  54.             if(!visited[poss1.mod])
  55.             {
  56.                 visited[poss1.mod]=1;
  57.                 q.push(poss1);
  58.             }
  59.  
  60.             poss2.s=hold.s;
  61.             poss2.s+='1';
  62.             poss2.mod=atoi(poss2.s.c_str())%num;
  63.             if(!visited[poss2.mod])
  64.             {
  65.                 visited[poss2.mod]=1;
  66.                 q.push(poss2);
  67.             }
  68.  
  69.         }
  70.  
  71.     }
  72.  
  73.     int main()
  74.     {
  75.         int t;
  76.         scanf("%d",&t);
  77.         while(t--)
  78.         {
  79.             int n;
  80.             scanf("%d",&n);
  81.             for(int i=0;i<20000+4;i++)
  82.                 visited[i]=0;
  83.  
  84.             bfs(n);
  85.         }
  86.  
  87.         return 0;
  88.     }
  89.  
  90.  
Success #stdin #stdout 0s 3360KB
comments (?)
stdin
copy 
3
17
11011
17
stdout
copy 
11101
11011
11101
https://ideone.com/16Utzu
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!