Find The Multiple

亦凉 2022-08-07 09:51 121阅读 0赞

Find The Multiple  
Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u  
Submit  
  
Status  
  
Practice  
  
POJ 1426  
Description  
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 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

#include <cstdio>
    #include <queue>
    using namespace std;
    
    __int64 a[205];
    
    
    void bfs(int n)
    {
        __int64 k;
        queue<__int64>Q;
        Q.push(1);
        while( !Q.empty() ){
            k=Q.front(); Q.pop();
            if(k%n==0)  { a[n]=k; return; }
            Q.push(k*10);
            Q.push(k*10+1);
        }
    }
    void get_a()
    {
        a[0]=0; a[1]=1; a[2]=10;
        for(int i=3; i<=200; i++){
            if(i%2==0) a[i]=a[i/2]*10;
            else bfs(i);
        }
    }
    
    int main()
    {
        int n;
        get_a();
        while(scanf("%d", &n)!=-1 && n!=0){
            printf("%I64d\n", a[n]);
        }
    
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，121人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 1426 找倍数 Find The Multiple（枚举+同余模应用）

同余模定理：（a\b）%n = （a%n \b%n）%n；（a+b）%n = （a%n +b%n）%n；详情[点击打开链接][Link 1] 题意：给出一

本是古典何须时尚/ 2024年02月17日 19:07/ 0 赞/ 81 阅读

相关 POJ 3279 Fliptile（二进制枚举、递推、POJ 1426 Find The Multiple、详解）

POJ 3279 Fliptile [测试平台][Link 1] Farmer John knows that an intellectually satisfied

左手的ㄟ右手/ 2022年12月05日 00:55/ 0 赞/ 146 阅读

相关 POJ1426-Find The Multiple (BFS 余数)

题意：给出一个整数n，(1 <= n <= 200)。求出任意一个它的倍数m，要求m必须只由十进制的'0'或'1'组成。第一份代码，记录路径的BFS 第二份代码，忘记是从

素颜马尾好姑娘i/ 2022年09月20日 12:50/ 0 赞/ 3 阅读

相关 POJ 1426-Find The Multiple【搜索】

Find The Multiple <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS

悠悠/ 2022年08月20日 14:14/ 0 赞/ 162 阅读

相关 Find The Multiple

Find The Multiple Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d &

亦凉/ 2022年08月07日 09:51/ 0 赞/ 122 阅读

相关 D - Find The Multiple POJ - 1426 ——DFS || BFS

Think: 1变量存储数值越界问题 2递归函数得到优解不再继续遍历问题 D - Find The Multiple POJ - 1426 Given a

深藏阁楼爱情的钟/ 2022年06月15日 01:28/ 0 赞/ 133 阅读

相关 POJ 1426 Find The Multiple(BFS和DFS)

[题目链接][Link 1] 题意：给你一个数n (1 <= n <= 200) ，求出一个任意的它的倍数，这个数只包含0或1。分析：首先暴力枚举肯定是不行的方法一：

矫情吗；*/ 2022年05月18日 01:11/ 0 赞/ 226 阅读

相关 POJ 1426 Find The Multiple ——————DFS

Find The Multiple Language:Default Find The Multiple <table> <tbody> <tr> <

雨点打透心脏的1/2处/ 2022年05月13日 05:34/ 0 赞/ 153 阅读

相关 POJ 1426 Find The Multiple

Find The Multiple <table> <tbody> <tr> <td><span style="font-size:16px;"><stro

女爷i/ 2021年09月30日 23:46/ 0 赞/ 200 阅读

相关 POJ 1426 Find The Multiple - DFS

[题目地址][Link 1] 分析: 　　简单DFS，也可以用BFS做，有看到其他博主的代码。　　找一个只含0和1的数ans是所输入的数n的倍数。　　第一位一定是1

╰+哭是因爲堅強的太久メ/ 2021年09月30日 09:14/ 0 赞/ 213 阅读