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

题目链接

题意：

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

题解：

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

AC代码：

#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;
}