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，(1 <= n <= 200)。求出任意一个它的倍数m，要求m必须只由十进制的'0'或'1'组成。
思路:
要不是放在这个搜索专题里我不会用搜索去解的,我肯定会暴力去解的;其实搜索也是一种枚举啊,
我这里用了两种方法;
dfs：
每个数都会有答案,因为都必须是0 1 组成的十进制，我们就每次去dfs他们的十倍和十倍+1;
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int flag;
void dfs(unsigned long long m,int x,int k)
{
if(flag||k>=19)//这里的flag标志位,找到了直接回溯返回
return ;
if(m%x==0)
{
flag=1;
printf("%I64u\n",m);
return ;
}
dfs(m*10,x,k+1);
dfs(m*10+1,x,k+1);
return ;
}
int main()
{
int n;
while(cin>>n&&n)
{
flag=0;
dfs(1,n,0);
}
return 0;
}
暴力:
将每个数存数组,然后根据存放位置的奇偶来决定是否+1，然后直到能整除！
#include<cstdio>
#include<iostream>
#define ll long long
#define N 6*100010
using namespace std;
ll a[N];
int n;
int main()
{
int i;
while(cin>>n&&n)
{
a[1]=1;//初始设置为1
int flag=0;
for(i=1;i<=N;i++)
{
a[i]=a[i/2]*10+i%2;//写几个数找一个规律,
if(a[i]%n==0)
{
printf("%lld\n",a[i]);
flag=1;
break;
}
}
}
return 0;
}
Marcus-Bao
认证博客专家
推荐系统
ACM算法竞赛
机器学习
本科毕业于国内知名四非大学，现中国科学院大学博士生，中国科学院计算技术研究所vipl实验室，老年ACM铁牌退役选手，喜欢算法竞赛，会点数据结构和算法，熟悉c++，python等；现阶段研究方向主要为机器学习与数据挖掘，比较关注推荐系统，发过顶会，炼过丹，平时博客主要记录些关于算法、数据结构，人工智能技术以及平时看的论文总结分享等，欢迎大家关注我，一起多多交流共同进步！
转载请注明原文地址: https://ju.6miu.com/read-661880.html
