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

Link

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.

Mean

给一个数N(1<=N<65536)，找一个N的倍数，使得这个倍数中不同数的个数最小，如果有多解，输出最小的。

Analysis

根据数论知识，任意一个数的倍数中一定存在一个两个数字表示的。

然后暴力搜索这两种情况即可。

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;
}