fork(1) 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.         ll value;
  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.value=1LL;
  32.         temp.mod=(temp.value)%num;
  33.         if(temp.mod==0)
  34.         {
  35.             printf("%d\n",num);
  36.             return;
  37.         }
  38.  
  39.         q.push(temp);
  40.         visited[temp.mod]=1;
  41.         while(!q.empty())
  42.         {
  43.             hold=q.front();
  44.             q.pop();
  45.  
  46.             if(hold.mod==0)
  47.             {
  48.                 printf("%lld\n",hold.value);
  49.                 break;
  50.             }
  51.  
  52.             poss1.value=hold.value;
  53.             poss1.value*=10;
  54.             poss1.mod=(poss1.value)%num;
  55.             if(!visited[poss1.mod])
  56.             {
  57.                 visited[poss1.mod]=1;
  58.                 q.push(poss1);
  59.             }
  60.  
  61.             poss2.value=hold.value;
  62.             poss2.value*=10;
  63.             poss2.value+=1;
  64.  
  65.             poss2.mod=(poss2.value)%num;
  66.             if(!visited[poss2.mod])
  67.             {
  68.                 visited[poss2.mod]=1;
  69.                 q.push(poss2);
  70.             }
  71.  
  72.         }
  73.  
  74.     }
  75.  
  76.     int main()
  77.     {
  78.         int t;
  79.         scanf("%d",&t);
  80.         while(t--)
  81.         {
  82.             int n;
  83.             scanf("%d",&n);
  84.             for(int i=0;i<20000+4;i++)
  85.                 visited[i]=0;
  86.  
  87.             bfs(n);
  88.         }
  89.  
  90.         return 0;
  91.     }
  92.  
  93.  
Success #stdin #stdout 0s 3356KB
comments (?)
stdin
copy 
3
17
11011
17
stdout
copy 
11101
11011
11101
https://ideone.com/nJbUXQ
language:
C++ (gcc 8.3)
created:
10 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!