【POJ - 1426】Find The Multiple（dfs）

-->Find The Multiple

原文是英语，直接上中文了

Descriptions:

给定一个正整数n，请编写一个程序来寻找n的一个非零的倍数m，这个m应当在十进制表示时每一位上只包含0或者1。你可以假定n不大于200且m不多于100位。 
提示：本题采用Special Judge，你无需输出所有符合条件的m，你只需要输出任一符合条件的m即可。

Input

输入包含多组数据，每组数据仅一行，只包含一个正整数n (1 <= n <= 200).

Output

对于输入的每组n，都输出任一符合条件的m。即使有多个符合条件的m，你也只需要输出一个即可。

Sample Input

Sample Output

题目链接：

https://vjudge.net/problem/POJ-1426

所求得的数只含有1或0，所以从1开始深搜，两个方向（n * 10） 或者（n * 10+1）。dfs终止条件：找到那个数或者这个数的长度大于19。 至于为何要大于19，很简单，long long最大值就是19位

AC代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 110
using namespace std;
int n,flag;
void dfs(int step,long long y)//step为数的长度，y为要寻找的数
{
    if(step>19 || flag==1)//利用flag保证找到这个数的时候终止
        return;
    if(y%n==0)
    {
        flag=1;
        cout << y << endl;
        return;
    }
    dfs(step+1,y*10);//两个方向
    dfs(step+1,y*10+1);
}
int main()
{
    while(cin >> n)
    {
        if(n==0)
            break;
        flag=0;
        dfs(1,1);//从1开始深搜，初始阶段长度为1
    }
}