POJ 1426 Find The Multiple(DFS)

POJ 1426 Find The Multiple(DFS)

http://poj.org/problem?id=1426

题意:给你一个[1,200]之间的整数n,要你求它的一个非0倍数m,这个m的十进制数只包含0和1.m不超过100位.

分析:

本题用常规思维去考虑这个100位就会很麻烦,因为题目中给的所有实例都是有unsigned long long的解的(这点我也是看别人题解的出来的,如果真要求100位左右的解需要用数组模拟大数,然后dfs),也就是说有<=19位的解的.所以我们直接DFS即可.

AC代码:

#include<cstdio>
using namespace std;
int flag;
int n;
void dfs(unsigned long long s,int step)
{
    if(flag==1 || step==19)
        return ;
    else if(s%n==0)
    {
        printf("%I64u\n",s);
        flag=1;
        return;
    }
    else
    {
        dfs(s*10,step+1);
        dfs(s*10+1,step+1);
    }
}
int main()
{
    while(scanf("%d",&n)==1&&n)
    {
        flag=0;
        dfs(1,0);
    }
    return 0;
}