题目描述

求解关于 $x$ 的同余方程

求满足条件的最小正整数解 $x_0$；如果该同余方程无解，则输出 $-1$。

输入格式

一行，三个正整数 $a,\ b,\ m$，用一个空格隔开。

输出格式

若有解，输出一行，一个正整数 $x_0$（最小正整数解）；否则输出一行，整数 $-1$。

样例

4 2 6

2

2 1 4

-1

说明/提示

方程有解当且仅当 $\gcd(a, m) \mid b$。求解时先约去 $\gcd$，再用扩展欧几里得求出 $a$ 对模 $m$ 的逆元，乘上 $b$ 后即得一个特解，最后将其调整到最小正整数即可。