fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define pb push_back
  3. #define ull unsigned long long int
  4. #define maxx 100
  5. #define sqF sqrt(5.0)
  6. #define phi (1+sqF)/2
  7. using namespace std;
  8. int X[]={+1,-1,-1,+1,+2,-2,+2,-2};
  9. int Y[]={+2,+2,-2,-2,+1,+1,-1,-1};
  10. map<string,bool>vis;
  11. bool check(string s,int n)
  12. {
  13.     int ans=0;
  14.     for(int i=0;i<s.length();i++)/**< This function is to check if our number in form of string is divisible by n or not */     
  15.      ans=(ans*10+s[i]-'0')%n;
  16.     ans=ans%n;
  17.     if(ans==0){ return true;}
  18.     return false;
  19. }
  20. string bfs(string s,int n)
  21. {
  22.     vis[s]=true;
  23.     queue<string>Q;
  24.     Q.push(s);
  25.     if(check(s,n))return s;
  26.     while(not Q.empty())
  27.     {
  28.         string src=Q.front();
  29.         if(check(src,n)==true)return src;
  30.         Q.pop();
  31.         string t=src+"1";
  32.         vis[t]=true;
  33.         string t2=src+"0";
  34.         vis[t2]=true;
  35.         Q.push(t2);
  36.         Q.push(t);
  37.     }
  38. }
  39. int main() {
  40.         ios_base::sync_with_stdio(false);
  41.         int t;
  42.     	cin>>t;
  43.     	while(t--)
  44.         {
  45.             int n;
  46.             cin>>n;
  47.             if(n==0)
  48.                 cout<<"0"<<endl;
  49.             else
  50.             {
  51.               string ans=bfs("1",n);
  52.               cout<<ans<<endl;
  53.             }
  54.             vis.clear();
  55.         }
  56.     return 0;
  57. }
  58.  
Success #stdin #stdout 0s 3244KB
comments (?)
stdin
copy 
3
17
11011
17
stdout
copy 
11101
11011
11101
https://ideone.com/izRX5O
language:
C++ (gcc 8.3)
created:
8 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!