http://www.carrefourstation.com

澳门新莆京手机网站POJ 1426 Find The Multiple

POJ 1426 Find The Multiple (广搜)

Find The Multiple

Time Limit: 1000MS

 

Memory Limit: 10000K

Total Submissions: 20235

 

Accepted: 8203

 

Special Judge

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

主题材料概略:给二个数n,求最小的k,使得k是n的整数倍,且k的十进制表示独有0和1.
难点上说那样的k不会超越200位,确实是当真,也才那样太可怕了,其实在1~200里的漫天n的结果k都以在61个人以内的,它极度说不当先200位,一同始把本人吓坏了,那题用广搜怎么或者做啊,太坑爹了那题。
广搜,其实这几个整体多少里最大的也可是是n=198时,k=1111111111111111110(不用数了,豆蔻年华共19个1,1个0卡塔尔国
AC代码:

#include 
#include 
using namespace std;
typedef __int64 ll;

void bfs(int n){
 queue que;
 que.push(1);
 while(!que.empty()){
  ll t=que.front();
  que.pop();
  if(t%n==0){
   printf("%I64dn",t);
   return ;
  }
  que.push(t*10);
  que.push(t*10+1);
 }
}

int main()
{
 int i,n;
 while(scanf("%d",&n),n)
  bfs(n);
 return 0;
}

下边还应该有二个代码,写的大约大器晚成致,只可是把bfs改成了__int64的带再次来到值,然后在main输出结果,W!A!了。。。。笔者不知晓,路过的大神帮助教导一下可好

#include 
#include 
using namespace std;
typedef __int64 ll;

ll bfs(int n){
 queue que;
 que.push(1);
 while(!que.empty()){
  ll t=que.front();
  que.pop();
  if(t%n==0)
   return t;
  que.push(t*10);
  que.push(t*10+1);
 }
}

int main()
{
 int i,n;
 while(scanf("%d",&n),n)
  printf("%I64dn",bfs(n));
 return 0;
}

1426 Find The Multiple (广搜) Find The Multiple Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 20235 Accepted: 8203 Special Judge Description Given a positive int...

POJ 1426 Find The Multiple

 

Find The Multiple

Time Limit: 1000MS

 

Memory Limit: 10000K

Total Submissions: 20297

 

Accepted: 8236

 

Special Judge

 

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 
#include 
#include 
#include 
#include 
#include 
#include 
#define N 1000009
#define ll __int64
using namespace std;

int n;
int flag;

void dfs(unsigned ll x,int k)//注意使用无符号64位整数
{
    if(flag) return;

    if(x%n==0)
    {
       printf("%I64un",x);
        flag=1;
        return;
    }

    if(k==19) return;//最大19位

    dfs(x*10,k+1);
    dfs(x*10+1,k+1);
}

int main()
{
    while(~scanf("%d",&n))
    {
        if(n==0) break;

        flag=0;

        dfs(1,0);
    }
    return 0;
}

 

 

 

 

 

 

1426 Find The Multiple Find The Multiple Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 20297 Accepted: 8236 Special Judge Description Given a positive integer n, w...

郑重声明:本文版权归澳门新莆京手机网站所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。