11月10日, 2016 1,934 views次
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; }