3648. 焉终的制剑限无

单点时限: 4.0 sec

内存限制: 512 MB

在固有结界“无限剑制”中,卫宫开始思考这样一个问题,如果把每一把剑看做数字 1,那么 $n$ 把剑连在一起模 $p$ 的余数是多少呢?卫宫只花了一瞬间就解决了这个简单的问题,不过他马上就忘记之前选的 $n$ 了,为了不让他被 master 打死,你能救救他吗?

一句话题意:已知 $p, k, c$,求最小的正整数 $n$ 使得 $\overbrace{ cc \cdots c }^{ n } \equiv k \pmod p$。

输入格式

输入包含一行三个整数 $p$, $k$, $c$ ($0 \leq k < p \leq 10^{12}, 1 \leq c \leq 9$)。

输出格式

输出最小的满足题意的 $n$,若无解,输出 -1

样例

Input
3 0 1
Output
3
Input
7 5 1
Output
4
Input
18 10 2
Output
5

提示

$\begin{aligned} 111 &\equiv 0 &\pmod 3 \
1111 &\equiv 5 &\pmod 7 \
22222 &\equiv 10 &\pmod {18} \end{aligned} $

8 人解决,66 人已尝试。

18 份提交通过,共有 564 份提交。

8.7 EMB 奖励。

创建: 1 年,8 月前.

修改: 1 年,8 月前.

最后提交: 2 月,1 周前.

来源: EOJ Monthly 2018.11

题目标签