P1988 火炬
题目描述
2008北京奥运会，你想成为四川汶川的一名火炬手，经过层层选拔，终于到了最后一关，这一关是一道很难的题：任意给定一个正整数N(N<=100000)，求一个最小的正整数M，使得N * M的十进制表示形式里只含有1和0。
输入输出格式
输入格式：
一行，输入一个整数N。
输出格式：
输出一行，如果有解，输出最小的M，否则输出“No Solution”
输入输出样例
输入样例#1：
12
输出样例#1：
925 看到这个题我们先想到的一定是枚举01字符串，看看最小的能被n整除的字符串的商即为答案。但是又有人要问了，怎么枚举01字符串？？两种方法，第一种为bfs，另一种为一个数的2进制数，我们知道01字符串从大到小排序一定就是挨个数字的2进制数我们先用第二种方法做一下
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 11000000
#define LL long long
using namespace std;
LL n,a[N];
int main()
{
scanf("%lld",&n);
;i;i++)
{
LL x=i,sum=,ans=;
while(x)
{
a[++sum]=x%;
x/=;
}
;i--) ans=ans*+a[i];
){printf(;}
}
;
}
我们再来用bfs A一下这道题
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 11000000
#define LL long long
using namespace std;
queue<LL>q;
LL n,a[N];
int main()
{
scanf("%lld",&n);
q.push();
while(!q.empty())
{
LL x=q.front();q.pop();
LL x1,x2;
x1=x*;
){printf(;}
else q.push(x1);
x2=x*+;
) {printf(;}
else q.push(x2);
}
;
}