大致方法就是认为任何一个只由0和1组成的数都是由若干个1eM组成的，然后背包里装的东西就是1eM % n就好了。
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

bool used[200];
bool tmp_used[200];
vector<int> graph[200];
int n;
int main() {
	while(cin >> n && n) {
		memset(used, 0, sizeof(used));
		for(int i=0; i<n; i++) {
			graph[i].clear();
		}
		int cnt = 1;
		while(n % 10 == 0) {
			cnt++; n /= 10;
		}
		while(n % 2 == 0) {
			cnt++; n /= 2;
		}
		while(n % 5 == 0) {
			cnt++; n /= 5;
		}
		if(n == 1) {
			cout << 1;
			for(int i=1; i<cnt; i++) {
				cout << 0;
			}
			cout << endl;
			continue;
		}
		used[1] = true;
		graph[1].push_back(cnt);
		int mod = 1;
		while(true) {
			cnt++;
			memcpy(tmp_used, used, sizeof(used));
			mod = (10*mod) % n;
			if(!tmp_used[mod]) {
				tmp_used[mod] = true;
				graph[mod].push_back(cnt);
			}
			for(int i=1; i<n; i++) {
				if(!used[i]) continue;
				int tmp = (mod+i) % n;
				if(!tmp_used[tmp]) {
					tmp_used[tmp] = true;
					graph[tmp] = graph[i];
					graph[tmp].push_back(cnt);
				}
			}
			memcpy(used, tmp_used, sizeof(used));
			if(used[0]) break;
		}
		// output
		int tmp;
		for(int i=graph[0].size()-1; i>=1; i--) {
			cout << 1;
			for(int j=graph[0][i]; j>graph[0][i-1]+1; j--) {
				cout << 0;
			}
		}
		cout << 1;
		for(int j=graph[0][0]; j>1; j--) {
			cout << 0;
		}
		cout << endl;
	}
	return 0;
}