自动搬运

查看原文

来自洛谷，原作者为

	BFqwq 青く广がった あの空のように、昙りなく笑えたら あなたに会いたい。

搬运于2025-08-24 22:20:15，当前版本为作者最后更新于2020-04-15 20:56:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

看了看题解区的题解，纠结了一下还是把官方题解发出来吧。

感觉做的都比较麻烦，仅有的几个贪心写法的基本也都没给证明。

以下是官方题解。

---

首先，我们分析输出 -1 的情况。

容易发现，当 $a=10$ 并且 $S$ 的第一个字符为 1 时显然无解，具体证明同样例二。

除此以外的情况都是有解的。证明如下：

对于 $1$ 位数的情况，显然有解。

假设对于 $k(k\ge 1)$ 位有解，则对于 $k+1$ 位一定有解。

假设 $k$ 满足前位的一个数为 $c$，

则只需证明 $c\times 10,c\times 10+1\ldots c\times 10+9$ 中必有一个数为 $a$ 的倍数，且必有一个不为 $a$ 的倍数。

熟知对于任意正整数 $m$，相邻的 $m$ 个正整数中，必有 $1$ 个数为 $m$ 的倍数，$m-1$ 个数不为 $m$ 的倍数。

由于 $a\ge 2$，$c\times 10,c\times 10+1\ldots c\times 10+a-1$ 为 $a$ 个相邻的整数，

故它们中必定有一个数为 $a$ 的倍数，$a-1(a-1\ge 1)$ 个不为 $a$ 的倍数。

故在接下来的讨论中排除无解的情况。

---

Subtask 1:

由于 $n$ 是正整数，在字符串长度为 $1$ 位的情况下，如果输入的串是 0 ，则 $1$ 显然是最小的答案。

如果输入的串是 $1$ ，则显然直接输出 $a$ 是最小的，因为 $a$ 的最小倍数就是 $a$ 本身。

---

Subtask 2:

对于 $n$ 为两位数的情况，我们可以选择直接打表，直接算出每种可能的对应最小解。

我们也可以采用枚举所有两位数逐个判断的方式。

当我们判断某一个数是否符合条件时，我们通过除以 $10$ 的方式得到其第一位，并判断其是否整除 $a$。

如果第一位符合条件，我们再直接判断其是否整除 $a$ 以判断前 $2$ 位是否满足条件。

---

Subtask 3:

与上面的做法相似，直接枚举所有 $6$ 位数。

不同的是对于每一个数我们要判断 $6$ 次。

我们通过除以 $100000$ 得到其第一位，通过除以 $10000$ 得到其前两位构成的数，以此类推。

对于每个数，逐一判断。先分离其第一位判断是否满足条件，若满足则分离前两位，以此类推。

由于 $6$ 位数一共只有 $900000$ 个，因此我们只需要经过不超过 $900000$ 次枚举就可以找到符合条件的数。

---

Subtask 4:

要判断一个数是否是 $2$ 的倍数只需要判断最后一位是否为 $2$ 的倍数 。

所以我们可以考虑从高位开始往后添加数字。

如果某一位是 1 ，则我们需要添加的数字是 $2\ 4\ 6\ 8\ 0$ 中的一个。本着最小的原则，我们选择 $0$ 。

同理，如果某一位是 0 则我们选择添加一个 $1$。

另外，如果字符串的第一位是 1 ，则我们需要进行特判。

---

Subtask 5:

考虑延续上面的做法，从高位往后添加数字。

由于我们是在高位上添加的，因此我们只需保证我们添加的数字最小，就一定是最优的。

对于第一位，如果第一位的字符是 0 则我们添加 $1$ 最优，否则第一位添加 $a$ 最优。

然后对于后面的每一位，设我们当前的数是 $n_1$ ，添加的数是 $j$ ，则得到的数是 $10\times n_1+j$。

由于 $j$ 只有十种可能性，分别枚举尝试，选取最小的加到数的尾端。

另外，由于 $n$ 过大，无法直接记录，故每添加一个数后对 $a$ 取模，然后输出时以字符串的方式输出。

---

以下是 std 代码。

#include <bits/stdc++.h>
using namespace std;
char c[100005],n[100005];
int a,b;
int now;
int main(){

	cin>>a>>b>>c;
	if(c[0]=='0')n[0]='1',now=1;
	else{
		if(a==10){
			puts("-1");
			return 0;
		}
		else n[0]=a+'0';
	};
	for(int i=1;i<b;i++){
		now*=10;
		for(int j=0;j<=9;j++)
		if((now+j)%a==0&&c[i]=='1'||(now+j)%a!=0&&c[i]=='0'){
			now+=j;
			now%=a;
			n[i]=j+'0';
			break;
		}
	}
	cout<<n;
	return 0;
}