HDU 4294 Multiple(搜索+数学)

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题意：

给定一个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;

}