> >
> > string Solution::multiple(int A) {
> > if(A == 1) return "1";
> > string s = "1";
> > vector<int>parent(A, -1);
> > vector<int>bit(A, -1);
> > queue<int>q;
> > parent[1] = 1;
> > q.push(1);
> > bit[1] = 1;
> >
> > while(q.size() > 0) {
> > int f = q.front();
> > q.pop();
> > if(f == 0) {
> > break;
> > }
> > int left = (f*10 + 0)%A;
> > int right = (f*10 + 1)%A;
> > if(parent[left] == -1) {
> > parent[left] = f;
> > bit[left] = 0;
> > q.push(left);
> > }
> > if(parent[right] == -1) {
> > parent[right] = f;
> > bit[right] = 1;
> > q.push(right);
> > }
> > }
> > string ans;
> > int curr = 0;
> > while(parent[curr] != curr) {
> > ans += to_string(bit[curr]);
> > curr = parent[curr];
> > }
> > ans += "1";
> > reverse(ans.begin(), ans.end());
> > return ans;
> > }
