← 返回题目列表

Codeforces · 303/D

D. 可旋转号码

中文机器翻译题面 查看原题

Bike是一个聪明的男孩,非常热爱数学。他受142857的启发,发明了一个叫做“可旋转数字”的数字。

如您所见,142857 是一个神奇的数字,因为它的任何旋转都可以通过将该数字乘以 1、2、...、6(从 1 到数字长度的数字)来获得。旋转一个数字意味着将其最后几位数字放入第一位。例如,通过旋转数字 12345,您可以获得任何数字:12345、51234、45123、34512、23451。值得一提的是,允许使用前导零。所以4500123和0123450都可以通过旋转0012345得到。你可以看到为什么142857满足条件。所有 6 个方程均以 10 为底。

- 142857·1 = 142857;
- 142857·2 = 285714;
- 142857·3 = 428571;
- 142857·4 = 571428;
- 142857·5 = 714285;
- 142857·6 = 857142.

现在,自行车有问题。他将“可旋转数”扩展到任何基数下 b.如上所述,142857 是基数 10 下的“可旋转数”。另一个例子是基数 2 下的 0011。所有 4 个方程都在基数 2 下。

- 0011·1 = 0011;
- 0011·10 = 0110;
- 0011·11 = 1001;
- 0011·100 = 1100.

因此,他想要找到最大的 b (1 < b < x),以便在基数 b 下存在长度为 n 的正“可旋转数”(允许有前导零)。

请注意,每当将可旋转数字乘以从 1 到其长度的数字时,您都应该得到该数字的旋转。

输入

唯一一行包含两个空格分隔的整数 n, x (1 ≤ n ≤ 5·106, 2 ≤ x ≤ 109)。

输出

打印一个整数——你找到的最大的 b。如果不存在这样的 b,则打印 -1。

示例

输入 #1

6 11

输出 #1

10

输入 #2

5 8

输出 #2

-1