自动搬运

查看原文

来自洛谷，原作者为

	唐一文 ‮‭

搬运于2025-08-24 21:42:10，当前版本为作者最后更新于2020-01-30 15:24:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

题解区里的方法都太深奥了，蒟蒻看不懂

思路 && Code

受到UVA1189的启发，我们可以先求出$01$串，再算出$B$。

认为数据一定很水的我立马打了个$dfs$，开了个$longlong$准备水过去：

#include<bits/stdc++.h>
using namespace std;
int n;
long long minn=LONG_LONG_MAX;
void dfs(long long ans,int k){
    if(k==20){//超出long long范围
		return ;
	}
    if(ans>minn){//剪枝
		return ;
    }
    if(ans%n==0){
        minn=min(minn,ans);//求最小值
        return ;
    }
    dfs(10*ans,k+1);
    dfs(10*ans+1,k+1);
}
int main(){
    cin>>n;
    dfs(1,1);
    cout<<minn/n<<" "<<minn;
    return 0;
}

然而，是这样的： $??!$
还是老老实实打高精度吧

把高精度模板一套：

#include<bits/stdc++.h>
using namespace std;
int n;
inline int mod(string a1){//求余数
	register int i;
	int b=0,len=a1.size();
	for(i=0;i<len;++i){
		b=((b<<1)+(b<<3)+(a1[i]^48))%n;
	}
	return b;
}
inline string chu(string a1){//高精度除法
	register int i;
	int s[10001],b=0,len=a1.size();
	for(i=0;i<len;++i){
		s[i]=((b<<1)+(b<<3)+(a1[i]^48))/n;
		b=((b<<1)+(b<<3)+(a1[i]^48))%n;
	}
	i=0;
	while(!s[i] && i<len){
		++i;
	}
	a1="";
	while(i<len){
		a1+=s[i]+'0';
		++i;
	}
	return a1;
}
string minn;
inline bool pd(string x){//判断是否超过已找到的最小值
	int lx=x.size(),ly=minn.size();
	if(lx<ly){
		return false;
	}
	if(lx>ly){
		return true;
	}
	register int i;
	for(i=0;i<lx;++i){
		if(x[i]<minn[i]){
			return false;
		}
		else if(x[i]>minn[i]){
			return true;
		}
	}
	return false;
}
void dfs(string ans){
	if(pd(ans)){
		return ;
	}
	if(!mod(ans)){
		minn=ans;
		return ;
	}
	dfs(ans+"0");
	dfs(ans+"1");
}
int main(){
	register int i;
	scanf("%d",&n);
	for(i=1;i<37;++i){//1~9999中答案的最大值
    /*
    不难发现，n为9的倍数时，答案总是很大
    当n=9999时最大
    那么n=9*1111
    因为9|111111111
    有9个1
    而1111有4个1
    又因为4和9互质
    所以minn=111...111(4*9=36个1)
    */
		minn+="1";
	}
	dfs("1");
	cout<<chu(minn)<<" "<<minn;
	return 0;
}

内心想法：我终于又水过了一道水蓝题$!$ $What?$
还会超时$?$

让我们重新看一下题目：
给出一个数$A$，你需要给出一个最小的数$B$，使得$A$与$B$的乘积只含有$0$和$1$

在学搜索时，求最小的答案一般用$bfs$更快
那么这题不就可以用$bfs$了吗

因为要求最小的，所以先插入$0$比先插入$1$更好
找到的满足条件的第$1$个数就是$B$

把$dfs$改成$bfs$：

#include<bits/stdc++.h>
using namespace std;
int n;
inline int mod(string a1){
	register int i;
	int b=0,len=a1.size();
	for(i=0;i<len;++i){
		b=((b<<1)+(b<<3)+(a1[i]^48))%n;
	}
	return b;
}
inline string chu(string a1){
	register int i,j;
	int s[10001],b=0,len=a1.size();
	for(i=0;i<len;++i){
		s[i]=((b<<1)+(b<<3)+(a1[i]^48))/n;
		b=((b<<1)+(b<<3)+(a1[i]^48))%n;
	}
	i=0;
	while(!s[i] && i<len){
		++i;
	}
	a1="";
	while(i<len){
		a1+=s[i]+'0';
		++i;
	}
	return a1;
}
string p;
queue<string>q;
int main(){
	register int i;
	scanf("%d",&n);
    //以下代码为改动了一点的bfs模板
	p="1";
	q.push(p);
	while(!q.empty()){
		p=q.front();
		q.pop();
		if(!mod(p)){ 
			cout<<chu(p)<<" "<<p;
			return 0;
		}
		q.push(p+"0");
		q.push(p+"1");
	}
	return 0;
}

这次总能过了吧$?$ $Excuse\ me?$ $MLE$是什么鬼$?!$

让我们手动模拟一下样例： |$p$ |$mod$ | | :----------: | :----------: | |$1$ |$1$ | |$10$ |$4$ | |$11$ |$5$ | |$100$ |$4$ | |$101$ |$5$ | |$110$ |$2$ | |$111$ |$3$ | |$1000$ |$4$ | |$1001$ |$5$ | |$1010$ |$2$ | |$1011$ |$3$ | |$1100$ |$2$ | |$1101$ |$3$ | |$1110$ |$0$ | 可以发现，有些数模$A$同余
根据同余的性质可得，它们乘上同一个数后模$A$也同余
因为要求最小的数，所以只要取这些数中最小的那一个数
用一个$bool$数组即可实现

因为我们是从小到大搜索的
所以第一个出现的数就是最小的那一个

AC Code

#include<bits/stdc++.h>
using namespace std;
int n;
inline int mod(string a1){
	register int i;
	int b=0,len=a1.size();
	for(i=0;i<len;++i){
		b=((b<<1)+(b<<3)+(a1[i]^48))%n;
	}
	return b;
}
inline string chu(string a1){
	register int i,j;
	int s[10001],b=0,len=a1.size();
	for(i=0;i<len;++i){
		s[i]=((b<<1)+(b<<3)+(a1[i]^48))/n;
		b=((b<<1)+(b<<3)+(a1[i]^48))%n;
	}
	i=0;
	while(!s[i] && i<len){
		++i;
	}
	a1="";
	while(i<len){
		a1+=s[i]+'0';
		++i;
	}
	return a1;
}
string p;
bool v[10005];//判断是否重复出现余数
queue<string>q;
int main(){
	register int i;
	scanf("%d",&n);
	p="1";
	q.push(p);
	while(!q.empty()){
		p=q.front();
		q.pop();
		if(!mod(p)){ 
			cout<<chu(p)<<" "<<p;
			return 0;
		}
        if(!v[mod(p+"0")]){//如果没有出现过这个余数
		    v[mod(p+"0")]=true;//这个数为最小的那一个，这个余数现在出现了，标记为true
            q.push(p+"0");
        }
        if(!v[mod(p+"1")]){//同上
            v[mod(p+"1")]=true;
		    q.push(p+"1");
        }
	}
	return 0;
}

（° - °)ノ✿ 完结撒花~