Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

直接用类似0/1背包的方法做，可以求最小的。

Posted by answer_zero at 2017-08-13 14:17:36 on Problem 1426
```大致方法就是认为任何一个只由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;
}```

Followed by: