题意：
给定一个n，让求一个M，它是n个倍数并且在k进制之下 M的不同的数字最少。
思路：
这里用到一个结论就是任意两个数可以组成任何数的倍数。知道这个之后就可以用搜索来做了。还有一个问题就是最多找n+1个数，因为由鸽巢原理，这n+1个数当中模上n一定有一个一同的。所以他们一减就是答案。如果找到直接是它的倍数的话，就直接返回。
搜索时保存的是它的余数，如果余数为0 的时候直接返回。还有就是在搜索中并不是直接找余数相同的两个数。而是找余数为0的。当暴力不同元素个数为2的时候，这时候已经算是找余数刚开始是由两个数相减得到的了。
#include <bits/stdc++.h> using namespace std;
const int maxn = 10005;
int n, k;
int num[2];
int fa[maxn];
char st[maxn];
bool bfs(int nums)
{
bool vis[maxn];
memset(vis, false, sizeof(vis));
queue<int> Q;
Q.push(0);
while (!Q.empty())
{
int u = Q.front(); Q.pop();
for (int i = 0; i < nums; i++)
{
int v = (u * k + num[i]) % n;
if (!vis[v] && !(u == 0 && num[i] == 0))
{
fa[v] = u;
st[v] = num[i] + '0';
vis[v] = true;
if (v == 0) return true;
Q.push(v);
}
}
}
return false;
}
bool cmp(string a, string b)
{
int len1 = a.length();
int len2 = b.length();
if (len1 != len2) return len1 < len2;
for (int i = 0; i < len1; i++)
if (a[i] != b[i]) return a[i] < b[i];
return 0;
} bool get_str(int u, string &str)
{
if (fa[u] != 0) get_str(fa[u], str);
str = str + st[u];
}
void update_ans(string &ans, string &str)
{
str = "";
get_str(0, str);
if (ans == "a" || cmp(str, ans))
ans = str;
}
int main()
{
while (~scanf("%d%d", &n, &k))
{
string ans = "a";
string str = "";
for (int i = 1; i < k; i++)
{
num[0] = i;
if (bfs(1))//找右一个数字构成的数
update_ans(ans, str);
}
if (ans == "a")//如果找不到一个的，就找两个的
{
for (int i = 0; i < k; i++)
{
for (int j = i + 1; j < k; j++)
{
num[0] = i;
num[1] = j;
if (bfs(2))
update_ans(ans, str);
}
}
}
cout << ans << endl;
}
return 0;
}