SQRT Problem
Burger 小姐有三个正整数 n,a,b。她想找到一个正整数 x(1≤x≤n−1),使它同时满足:
- x2≡a(modn);
- ⌊3x2⌋=b。
保证 n 是奇数,且 gcd(a,n)=1,其中 gcd(u,v) 表示 u,v 的最大公约数。还保证满足条件的解存在且唯一。
记号 ⌊t⌋ 表示不超过 t 的最大整数。例如:⌊0.5⌋=0、⌊11.3⌋=11、⌊101.9⌋=101、⌊99⌋=99、⌊0⌋=0、⌊2⌋=2。
输入格式
第一行包含一个整数 n(3≤n≤10100−1)。
第二行包含一个整数 a(1≤a≤n−1)。
第三行包含一个整数 b(1≤b≤n−1)。
输入只有一组 n,a,b,所有整数均以十进制表示。n 不一定是素数。
输出格式
输出一个整数,表示唯一的解 x。
样例 1
9
4
3
7
样例 2
650849
253233
5059
359895
样例 3
29268658540371639122046169677605538931
22216978925831646928504047924228222624
9226521123963832612770162
28025732380501848167087889769592298758