当前位置: 代码迷 >> 综合 >> POJ1426 Find The Multiple(DFS||BFS||同余模定理)
  详细解决方案

POJ1426 Find The Multiple(DFS||BFS||同余模定理)

热度:29   发布时间:2024-01-16 13:51:15.0

题意:

给出一个数,寻找这个数的倍数,要求只能由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;
}


  相关解决方案