fork(1) download
copy 
  1. # include <iostream>
  2. # include <string>
  3. # include <cstdio>
  4. # include <cstring>
  5. # include <queue>
  6. using namespace std;
  7.  
  8. int Input;
  9. bool exist[20000];
  10. int parent[20000];
  11. char digit[20000];
  12. char buffer[51];
  13.  
  14. int main(int argc, char const *argv[])
  15. {
  16.     int N,remainder,current;
  17. 	cin >> N;
  18. 	for (int i = 0; i < N; i++)
  19. 	{
  20. 		cin >> Input;
  21. 		queue <int> Queue;
  22. 		memset(exist,0,sizeof(exist));
  23. 		if (Input == 1)
  24. 		{
  25. 			cout << "1" << endl;
  26. 			continue;
  27. 		}
  28. 		parent[1] = -1;
  29. 		digit[1] = '1';
  30. 		exist[1] = true;
  31. 		Queue.push(1);
  32. 		while (!Queue.empty())
  33. 		{
  34. 			current = Queue.front();
  35. 			Queue.pop();
  36. 			remainder = current * 10;
  37. 			remainder %= Input;
  38. 			if(!exist[remainder])
  39. 			{
  40. 				exist[remainder] = true;
  41. 				parent[remainder] = current;
  42. 				digit[remainder] = '0';
  43. 				if(remainder==0) break;
  44. 				Queue.push (remainder);
  45. 			}
  46. 			remainder++;
  47. 			remainder %= Input;
  48. 			if(!exist[remainder])
  49. 			{
  50. 				exist[remainder] = true;
  51. 				parent[remainder] = current;
  52. 				digit[remainder] = '1';
  53. 				if(remainder==0) break;
  54. 				Queue.push (remainder);
  55. 			}
  56. 		}
  57. 		int len = 0;
  58. 		current = 0;
  59. 		while(true)
  60. 		{
  61. 			buffer[len++] = digit[current];
  62. 			if(parent[current] >= 0)
  63. 				current = parent[current];
  64. 			else break;
  65. 		}
  66. 		while((--len)>=0)
  67. 		{
  68. 			cout << buffer[len];
  69. 		}
  70. 		cout << endl;
  71. 	}
  72. 	return 0;
  73. }
  74.  
Success #stdin #stdout 0.02s 2936KB
comments (?)
stdin
copy 
3
17
11011
19998
stdout
copy 
11101
11011
1111111111111111111111111111111111110
https://ideone.com/3nlO2d
language:
C++ (gcc 8.3)
created:
13 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!