jzoj3058 火炬手

题目大意

链接
给出一个$n$，求一个最小的$m$使$n\ast m$的十进制只由0和1构成。

解题思路

考场上以为是数论推了半天最后交了暴力，赛后发现因为n比较小导致除了极限数据以外$n\ast m$的结果都不会超过20位，搜索就能过。开long long 枚举n*m当前的第$i$位是0还是1，搜到能整除n的就返回。
如果怕第一次搜到的不是最小的结果可以把搜到的所有答案存到数组里最后再排序。
本来99后面多加几个9都会爆但是数据太弱被水过去了

代码

#include
using namespace std;
int n,tot;
unsigned long long minn=0;
void dfs(unsigned long long x,int dep)
{
	if(dep>19) return;
	if(x%n==0&&(minn==0||x<minn)) minn=x;
	dfs(x*10,dep+1);
	dfs(x*10+1,dep+1);
}
int main()
{
	cin>>n;
	dfs(1,1);
	cout<<minn/n;	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

心疼隔壁打高精度结果没有极限数据的fjy