【纪中】2022.7.13 3058.火炬手

• 前言
• 原题网址
• 题目描述
• 格式
• • 输入格式
  • 输出格式
• 样例
• • 输入样例
  • 输出样例
• 提示
• 解题思路
• Code

好久没写博客了，可能有点生疏，如有不当请在评论区指出喔~
来到了纪中，每天打比赛，有点累了，~~~~(>_<)~~~~。

由于某些原因，这个网址会进不去…

全运会就要开始了，笨笨想成为湖南地区的火炬手，经过层层选拔，最终到了最后一关，这一关给出了一个正整数 n n n，求一个最小的正整数 m m m，使得 n ∗ m n*m n∗m的十进制表示形式中只含 1 1 1和 0 0 0。

一行一个数 n n n。

输出一行，如果有解，输出最小的 m m m，否则输出 ‘no solution’。

12

925

n ≤ 100000 nle100000 n≤100000

作为两天内唯一靠自己A掉的题目， 这道题其实还是很有挑战性的，我想了好久才想出非正解，并且有多种做法，我使用的是玄学DFS（广度优先搜索） 算法。
其实就是枚举 01 01 01串的每一位，就是位数有点大，对于一些特定的 n n n，其对应的 m m m可能多达 ∞ infin ∞位（开个玩笑）。

过 · 于 · 详 · 细

#include // 头文件
#define integer unsigned long long // 习惯
using namespace std; // 命名空间
integer n; // 定义n
queue q; // 定义队列
void bfs(integer first) { // 定义bfs
	while(!q.empty()) { // 先清空
		q.pop(); // 弹出
	} // 清空结束
	q.push(first); // 把初始值放进去
	while(!q.empty()) { // 其实不需要!q.empry()，因为是靠下面的return退出函数
		integer m=q.front(); // 获取第一个元素
		q.pop(); // 弹出
		if(m%n==0) { // 找到了
			cout< // 主函数开始
	cin>>n; // 输入
	bfs(1); // 开始bfs，初始值为1
	return 0; // 结束
} // 主函数结束

像这么详细的程序一般肯定不是正解， 正解还需要打高精度，否则根本无法面对像99999这样刁钻的 n n n的数据。