4997.解方程

时间限制:1s 内存限制:256MB

给定两个质数 $p,q$,求二次方程 $x^2+py^2=1$
的正整数解。

输入格式(从终端/标准输入读取)

第一行一个正整数 $T$(1≤T≤10^4)$,表示数据组数。

对于每组数据,一行两个质数 $p,q(2\lt p\lt q\lt 2^{60} )$,表示方程的系数。

输出格式(输出至终端/标准输出)

对于每组数据,如果方程无解,则输出 $−1$,否则输出两个正整数 $x,y$,表示方程的解。

可以证明,若方程有正整数解,则解唯一。

输入样例

复制
3
29 569
17 757
19 619
 \n
  ·   \n
  ·   \n
  ·   \n

输出样例

复制
-1
-1
12 5
  \n
  \n
  · \n
来源: 2024“钉耙编程”中国大学生算法设计超级联赛(6)

提交题解

Please login first.

© 2025 FAQs