51nod 1109 01组成的N的倍数（bfs）

Description

给定一个自然数 N ，找出一个 M ，使得 M > 0 且 M 是 N 的倍数，并且 M 的 10 进制表示只包含 0 或 1 ，求最小的 M 。

例如：N = 4，M = 100。

Input

输入 1 个数 N 。(1 <= N <= 10^6)

Output

输出符合条件的最小的 M 。

Sample Input

Sample Output

思路

POJ 1426 的强化版本，主要是数据的增加。

随着数据范围的扩大，我们搜索的解空间也会相应的成指数级上升，于是这里要考虑一个很好的剪枝：

我们知道， $13\%3=((1 \times 10)\%3+3)\%3$

即，两个数的前缀模一个数的结果相等时，最终结果是否相等由其后缀唯一决定。

于是，我们在考虑搜索时，存在相同的前缀模即剪枝的条件。

PS：C++ 中的 string 类型虽然好用，但只有最后一组数据不能通过（TLE），最后一组数据是 738169 。

PPS：单纯用数组来存储会 MTE ，我们需要考虑动态分配内存。

PPPS：有种暴力的感觉，当然存在更优秀的解法啦~（出门右拐某大神博客

AC 代码

#include<bits/stdc++.h>
using namespace std;
typedef __int64 LL;
const int maxn = 1e6+10;
int n,tot;
bool vis[maxn];
queue<char*>sk;

int multget(char* s,int len)
{
    int ans=0;
    for(int i=0; i<len; i++)
        ans=(ans*10+s[i]-'0')%n;
    return ans;
}

void push(const char* s,int len,char c)
{
    char *ne = (char*)malloc(len+2);
    strcpy(ne,s);
    ne[len]=c;
    ne[len+1]=0;
    sk.push(ne);
}

void bfs()
{
    push("",0,'1');
    while(!sk.empty())
    {
        char* s=sk.front();
        sk.pop();
        int len = strlen(s);
        int num = multget(s,len);
        if(num==0)
        {
            puts(s);
            return;
        }
        if(!vis[num])
        {
            push(s,len,'0');
            push(s,len,'1');
            vis[num]=true;
        }
        free(s);
    }
}

int main()
{
    cin>>n;
    bfs();
    return 0;
}