#P220. Lucky Number

    ID: 158 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及- 上传者: 标签>选拔2.0赛制:OI来源:wyfoj http://127.0.0.1枚举

Lucky Number

Lucky Number

题目描述

致远觉得他有个lucky number,会给他带来幸运,他会给出一个数 a,以及一个长度为 b 的 01 串 S。

简单的说,他的 Lucky Number 是满足以下条件的正整数 n:

n 的位数为 b 且不含前导 0。

若 S 的第 i 位为 1,则 n 的前 i 位组成的数是 a 的倍数,否则 n 的前 i 位组成的数不是 a 的倍数。

对于一个数,前 i 位组成的数是指这个数前 i 个数码依次拼接形成的数。例如 3123111 前 3 位组成的数为 312,前 5 位组成的数为 31231。

现在,请你帮助致远计算一下,他的 Lucky Number 是多少。

由于满足条件的数可能会有多个,你需要输出最小的一个。若不存在,则请输出 -1

输入格式

输入数据由两行构成。

第一行两个整数 a,b,意义见题目描述。

第二行一个长度为 b 的字符串 S。

输出格式

一行,满足条件的最小的数 n。如果不存在满足条件的数,输出 -1。

数据范围

(原站未提供,导入后需人工补齐)

样例

2 2
01
10
10 1 
1
-1
6 6
110100
601210

提示

【样例解释】

对于样例一,10是 2 位数,且 10 的前 1 位组成的数 1 不是 2 的倍数,而前 2 位组成的数 10 是 2 的倍数。由于 10 已经是最小的两位数,故不存在比 10 更小的满足条件的数。

对于样例二,我们需要构造一个 1 位数,满足这个 1 位数能被10整除。显然,这样的数不存在。

对于全部数据,保证2≤a≤10,1≤b≤9,S中只包含0和1。