Find The Multiple（DFS）

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. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.

Input The input file may contain multiple test cases. Each line contains a value of n (1 ≤ n ≤ 200). A line containing a zero (0) terminates the input.

Output For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.

Sample Input 2 6 19 0

Sample Output

100100100100100100

111111111111111111

个人心得：这题开始没看懂，原来是求所求数的倍数，但这个倍数只由0，1组成，有俩种版本，一个是longlong直接过，这个在数据较多的时候不容易过，

先说下longlong吧，就是从1开始深搜，有2种方向，一是乘以10，二是乘以10再加1，这个简单深搜还是比较好实现的。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<queue>

 #include<algorithm>

 using namespace std;

 int n,flag;

 unsigned long long ans;

 void dfs(unsigned long long x,int y)

 {

   if(y>) return ;

     if(x%n==)

     {

         flag=;

         ans=x;

         return;

     }

     else

       {for(int i=;i<;i++)

         dfs(*x+i,y+);

       }

         if(flag) return;

 }

 int main()

 {

   unsigned long long x;

   while(cin>>n)

   {

       if(n==) break;

       x=;

       flag=;

       dfs(x,);

       cout<<ans<<endl;

   }

   return ;

 }

再看一下数组存储的代码，他这个涉及到的知识点真的不知道，每次得到新数都进行取余再将这个数放入数组里，这样就不会数据溢出了，一开始想这么做怕担心

数据会溢出。

 #include <iostream>

 using namespace std;

 int n, t, a[], ac,l;

 void dfs(int c, int s)

 {

          if(s==)//如果余数为0，择停止递归

          {

                    ac = ;//表示已经找到结果

                    l=c;//给数组的长度赋值

          }

          else if(c < )//在深度100范围内进行递归

          {

                    if(ac==)//还没找到结果，进行递归运算

                    {

                             a[c] = ;//尝试下一位放1

                             dfs(c + , (s *  + ) % n);

                    }

                    if(ac==)

                    {

                             a[c] = ;

                             dfs(c + , (s * ) % n);

                    }

          }

 }

 int main()

 {

          while(cin>>n,n)

          {

                    a[] = , ac = ;//初始化

                    dfs(, );

                    for(int i=;i<l;i++) cout<<a[i];//根据递归得到的结果，进行输出

                    cout<<endl;

          }

          return ;

 }

巴特西

Find The Multiple（DFS）

最新文章

热门文章