Top

POJ - 1426 - Find The Multiple(双入口DFS)


题目链接

题意:

给一个数n,让你找出一个只有1,0,组成的十进制数,要求是找到的数可以被n整除

题解:

用DFS是搜索 当前位数字 (除最高位固定为1),因为每一位都只有0或1两种选择

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;
const int maxn=230;
int n;
bool found;
void dfs(ll ans,int k){
if(found)return;
if(ans%n==0){
printf("%llu\n",ans);
found=1;
return;
}
if(k==19)return;
dfs(ans*10,k+1);
dfs(ans*10+1,k+1);
}
int main(){
while(scanf("%d",&n)&&n){
found=0;
dfs(1,0);
}
return 0;
}
文章版权为Anoyer博客所有,转载请以链接形式标明本文地址