#P18456. SQRT Problem

    ID: 17792 传统题 3000ms 256MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3200NOI/NOI+/CTS向下取整与向上取整同余的加减乘运算高精度整数平方根高精度乘法归一化长除法LLL 格基约化

SQRT Problem

SQRT Problem

Burger 小姐有三个正整数 n,a,bn,a,b。她想找到一个正整数 xx(1≤x≤n−11\le x\le n-1),使它同时满足:

  • x2≡a(modn)x^2\equiv a\pmod n;
  • ⌊x23⌋=b\left\lfloor\sqrt[3]{x^2}\right\rfloor=b。

保证 nn 是奇数,且 gcd⁡(a,n)=1\gcd(a,n)=1,其中 gcd⁡(u,v)\gcd(u,v) 表示 u,vu,v 的最大公约数。还保证满足条件的解存在且唯一。

记号 ⌊t⌋\lfloor t\rfloor 表示不超过 tt 的最大整数。例如:⌊0.5⌋=0\lfloor0.5\rfloor=0、⌊11.3⌋=11\lfloor11.3\rfloor=11、⌊101.9⌋=101\lfloor101.9\rfloor=101、⌊99⌋=99\lfloor99\rfloor=99、⌊0⌋=0\lfloor0\rfloor=0、⌊2⌋=2\lfloor2\rfloor=2。

输入格式

第一行包含一个整数 nn(3≤n≤10100−13\le n\le10^{100}-1)。

第二行包含一个整数 aa(1≤a≤n−11\le a\le n-1)。

第三行包含一个整数 bb(1≤b≤n−11\le b\le n-1)。

输入只有一组 n,a,bn,a,b,所有整数均以十进制表示。nn 不一定是素数。

输出格式

输出一个整数,表示唯一的解 xx。

样例 1

9
4
3
7

样例 2

650849
253233
5059
359895

样例 3

29268658540371639122046169677605538931
22216978925831646928504047924228222624
9226521123963832612770162
28025732380501848167087889769592298758