poj 1426 Find The Multiple
http://poj.org/problem?id=1426
题意：Given a positive integer n, write a program to find out a nonzero multiple(倍数) m of n whose decimal(十进制) representation contains only the digits 0 and 1. （ n<200 , m的位数最多为100 ）
分析：正向思维会想到暴力，判断n的倍数m是否满足，1000ms超时，且需要处理大数。
但反过来想，怎样才能出现十进制都是由1,0构成的数呢，不就是对1不断的乘10或乘10加1，写一个深度为100的深搜，这样最坏循环100*100，不会超时。
但是深度为100 的话 得到的数存不下啊
宽搜得到的解中，最长的为198,19位数，因此用unsigned long long 存数就可以，写一个深度为19的深搜ok
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <algorithm> 5 #include <cstdio> 6 #include <cstring> 7 #include <cmath> 8 #include <stack> 9 #include <queue> 10 #include <functional> 11 #include <vector> 12 #include <map> 13 /*10^8-----1s*/ 14 using namespace std; 15 //#define M 0x0fffffff 16 #define M 1000000004 17 #define min(a,b) (a>b?b:a) 18 #define max(a,b) (a>b?a:b) 19 #define N 1001 20 int flag,n; 21 void dfs(unsigned long long x,int deep) 22 { 23 if(deep==19||flag) 24 return ; 25 if(x%n==0) 26 { 27 flag=1; 28 printf("%I64u\n",x); 29 return ; 30 } 31 dfs(x*10,deep+1); 32 dfs(x*10+1,deep+1); 33 } 34 int main() 35 { 36 37 while(scanf("%d",&n)&&n) 38 { 39 flag=0; 40 dfs(1,0); 41 } 42 return 0; 43 }
原文：http://www.cnblogs.com/bibier/p/3952037.html
