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

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

4

Sample Output

100

思路

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

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

我们知道， 13%3=((1×10)%3+3)%3

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

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

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

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

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

AC 代码

#includeusing namespace std;typedef __int64 LL;const int maxn = 1e6+10;int n,tot;bool vis[maxn];queuesk;int multget(char* s,int len){ int ans=0; for(int i=0; i>n; bfs(); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。