POJ1426 Find The Multiple（DFS||BFS||同余模定理）

本文主要是介绍POJ1426 Find The Multiple（DFS||BFS||同余模定理），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

给出一个数，寻找这个数的倍数，要求只能由0和1组成

要点：

可以用BFS和DFS做，用BFS做只能用G++过，C++会超时。用DFS可以避免这些问题，但深度要自己猜一个数，来过oj的数据，有点投机取巧。最好是用同余模定理，但是别人的博客我有点看不懂。

参考博客：同余模定理做法

DFS：

15298844

Seasonal

1426

Accepted

168K

125MS

C++

369B

2016-03-22 08:36:59

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int n;
bool found;void dfs(unsigned __int64 num,int k)
{if (found)//找到就不再找了，否则会输出多个return;if (num%n == 0){found = true;printf("%I64u\n", num);return;}if (k == 19)//因为dfs是先找全0的，所以必须设定一个深度，就算没有找到也得返回return;dfs(num * 10,k+1);dfs(num * 10 + 1,k+1);
}int main()
{while (~scanf("%d", &n),n){found=false;dfs(1,1);}return 0;
}

BFS：

15299406

Seasonal

1426

Accepted

2788K

235MS

G++

483B

2016-03-22 14:18:02

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
using namespace std;
int n;void bfs()
{queue<__int64> que;que.push(1);int i;__int64 x, pos;while (!que.empty()){pos = que.front(); que.pop();for (i = 0; i <= 1; i++){x = pos * 10 + i;if (x%n == 0){printf("%I64d\n", x);return;}que.push(x);}}
}int main()
{while (~scanf("%d", &n), n){if (n == 1)printf("1\n");//少做一个1可以节省很多内存和时间elsebfs();}return 0;
}

这篇关于POJ1426 Find The Multiple（DFS||BFS||同余模定理）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---