洛谷【UVA1189 Find The Multiple】——不用大数计算，使用广搜与深搜快速解决

我不是女神ヾ 2022-10-23 14:29 7阅读 0赞

Description  
Given a positive integer n, write a program to ﬁnd 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 ﬁle 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  
10  
100100100100100100  
111111111111111111

--------------------

**题意翻译**  
**题目描述**  
给出一个整数n，(1 <= n <= 200)。求出任意一个它的倍数m，要求m必须只由十进制的’0’或’1’组成。

**输入输出格式**  
**输入格式：**  
输入文件可能包含多个测试样例。每行包含一个 n (1 < = n < = 200) 。包含零的行将终止输入。

**输出格式：**  
对于输入中的n , 输出对应的 m 。m 用十进制表示，不能超过100位。如果 n 有多个解决方案, 则其中任何一个都是可以的。

**输入输出样例**  
**输入样例：**

2
    6
    19
    0

**输出样例：**

10
    100100100100100100
    111111111111111111

感谢@zhuyifan 提供的翻译

**输入输出样例**  
无

--------------------

此题来自洛谷，提交地址在[【UVA1189 Find The Multiple】][UVA1189 Find The Multiple]，虽然是UVA1189 Find The Multiple，但是洛谷也能提交。

这道题比较迷惑，其实我们稍加计算就可以发现，输入6——输出100100100100100100是一个忽悠人的行为，题目就是会迷惑人。1110不就可以整除6吗！

所以这道题用long long就可以，这道题不配 普及+

![在这里插入图片描述][2021030520284954.png_pic_center]  
就是这样的题，也不要用暴力，最好使用以下搜索——深搜或者广搜。

首先先做一个变量t=1，然后每次存入t×10+1 和 t×10+0 这样可以做到这个数中只有1和0，然后每次判断t÷6==0。这道题就可以依据这个做成深搜的递归式和广搜的队列。

第一种方法——深搜

#include<iostream>
    #include<cstring>
    using namespace std;
    int n,k;//k 开关
    void dfs(unsigned long long ans,int n,int index)//ans 答案 n mod index 位数
    { 
        if(k==0)return;
        if(index==20)return;//范围
        if(ans%n==0)//数据过水不需要大整数
        { 
            cout<<ans<<endl;
            k=0;
            return;
        }
        dfs(10*ans,n,index+1);//奇数
        dfs(10*ans+1,n,index+1);//偶数
    }
    int main()
    { 
        while(scanf("%d",&n)&&n!=0)
        { 
            k=1;
            dfs(1,n,1);
        }
        return 0;
    }

第二种方法——广搜

#include <iostream>
    #include <queue>
    #include <cstdio>
    
    using namespace std;
    #define ULL unsigned long long
    ULL n;
    
    ULL BFS() { 
        queue<ULL> q;
        ULL ans, tail;
        ULL xx;
        q.push(1);
        while (!q.empty()) { 
            tail = q.front();
            q.pop();
            for (int i = 0; i < 2; i++) { 
                xx = tail * 10 + i;
                if (xx % n == 0) { 
                    return xx;
                } else { 
                    q.push(xx);
                }
            }
        }
    }
    
    int main() { 
        while (true) { 
            cin >> n;
            if (n == 0)
                break;
            ULL ans;
            ans = BFS();
            cout << ans << endl;
        }
        return 0;
    }

[UVA1189 Find The Multiple]: https://www.luogu.com.cn/problem/UVA1189
[2021030520284954.png_pic_center]: /images/20221023/159c6c68cf594cb4a6dcc1d440e28d54.png