首页 > 代码库 > poj 1426 Find The Multiple

poj 1426 Find The Multiple

2024-07-20 20:05:58   222人阅读

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 0x0fffffff16 #define M 100000000417 #define min(a,b) (a>b?b:a)18 #define max(a,b) (a>b?a:b)19 #define N 100120 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 }
View Code

 

poj  1426  Find The Multiple






























        

            
                
                  
                
                

                    联系

                    我们