构造全球化 - 代码源竞赛平台

题目描述

众所周知，中文名是姓在前名在后，英文名是名在前姓在后。

数学王国中，每个人的姓名由两个十进制数字串组成，分别称为姓和名。现已知某人的姓为 $A$ ，其中 $A$ 由十进制数字组成，首位不为 $0$ 。现在需要为他确定一段非空的名 $B$ ， $B$ 的首位也不能为 $0$ 。

姓名可能按照姓在前、名在后的顺序书写，也可能按照名在前、姓在后的顺序书写。无论采用哪一种写法，拼接得到的整数都必须能被给定的正整数 $m$ 整除。拼接时，两段数字内部的顺序保持不变。例如，若某人的姓为 $12$ 、名为 $34$ ，两种写法分别得到 $1234$ 和 $3412$ 。

请找出长度最短的名 $B$ 。若有多个最短的名，输出任意一个即可；若不存在符合要求的名，输出 NO。

第一行包含一个正整数 $m$ ，为整除条件中的除数。

第二行包含一个数字串 $A$ ，为这个人的姓。

若无解，输出一行 NO。

否则，输出一行数字串 $B$ ，表示一个长度最短的合法名。 $B$ 非空，首位为 $1$ 至 $9$ 中的数字，其余各位为 $0$ 至 $9$ 中的数字。

7
1

8
12

NO

10
10

样例 1：按照姓在前、名在后的顺序，以及名在前、姓在后的顺序书写，分别得到 $110005$ 和 $100051$ ，都能被 $7$ 整除。不存在长度小于 $5$ 的合法名。

样例 2：不存在能同时满足两种姓名书写顺序下整除要求的名。

样例 3：两种姓名书写顺序得到的整数都为 $1010$ 。不存在长度为 $1$ 的合法名。

本题各子任务单独计分。须通过某子任务包含的所有测试点，方可获得该子任务的分数。

子任务编号	分数	$m\le$	特殊性质
$1$	$20$	$20$	$\lvert A\rvert\le 6$
$2$	$30$	$2000$	$\lvert A\rvert\le 2000$
$3$	$15$	$2 \times 10^5$	特殊性质 A
$4$	$35$	$2 \times 10^5$	无

特殊性质 A： $A$ 表示的整数能被 $m$ 整除。

对于 $100\%$ 的数据， $1\le m\le 2 \times 10^5$ ， $1\le |A|\le 2 \times 10^5$ 。 $A$ 的首位为 $1$ 至 $9$ 中的数字，其余各位为 $0$ 至 $9$ 中的数字。