HDU 1664 – Different Digits [数论+暴力BFS]

http://acm.hdu.edu.cn/showproblem.php?pid=1664

Problem

Given a positive integer n, your task is to find a positive integer m, which is a multiple of n, and that m contains the least number of different digits when represented in decimal. For example, number 1334 contains three different digits 1, 3 and 4.

Code

```#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;

const int maxn = 66666;
int N;
int cur[maxn], pre[maxn];
bool vis[maxn];

string ans;

void setAns(const string &x) {
if(ans.empty()) ans = move(x);
else if(x.size() < ans.size()) ans = move(x);
else if(x.size() == ans.size() && x < ans) ans = move(x);
}

void solve1(int x) {
memset(vis, false, sizeof(bool) * N);
int cur = x % N, cnt = 1;
while(!vis[cur]) {
vis[cur] = true;
if(cur == 0) break;
cnt += 1;
cur = (cur * 10 + x) % N;
}
if(vis[0]) setAns(string(cnt, x + '0'));
}

void solve2(int x, int y) {
memset(cur, -1, sizeof(int) * N);
memset(pre, -1, sizeof(int) * N);
queue<int> qu;
if(x != 0) qu.push(x % N), cur[x % N] = x;
if(y != 0) qu.push(y % N), cur[y % N] = y;
while(!qu.empty()) {
int u = qu.front(), v; qu.pop();
if(u == 0) break;
v = (u * 10 + x) % N;
if(cur[v] == -1) qu.push(v), cur[v] = x, pre[v] = u;
v = (u * 10 + y) % N;
if(cur[v] == -1) qu.push(v), cur[v] = y, pre[v] = u;
}
if(cur[0] != -1) {
string str;
int t = 0;
while(t != -1) {
str.push_back(cur[t] + '0');
t = pre[t];
}
reverse(str.begin(), str.end());
setAns(str);
}
}

int main() {
while(scanf("%d", &N), N) {
ans.clear();
for(int i = 1; i <= 9; ++i)
solve1(i);
if(ans.empty())
for(int i = 0; i <= 9; ++i)
for(int j = i + 1; j <= 9; ++j)
solve2(i, j);
printf("%s\n", ans.c_str());
}
return 0;
}
```