#P8335. [2023广东省队集训]平方和

    ID: 8418 传统题 1000ms 888MiB 尝试: 3 已通过: 2 难度: 9 上传者: 标签>CF2600省选/NOI-整数二平方和判定Miller–RabinPollard–Rho二次剩余快速幂随机采样两平方和恒等式单调量证明终止快速乘防溢出

[2023广东省队集训]平方和

题目描述

给定正整数 nn,求两个非负整数 x,yx,y,使得 x2+y2=nx^2+y^2=n。有多个解时,可以输出任意一组。

原赛向选手提供了一份 Pollard–Rho 质因数分解模板。

输入格式

第一行一个整数 TT,表示测试组数。接下来 TT 行,每行一个正整数 nn。

输出格式

每组输出一行。无解时输出 -1。有解时输出两个非负整数 x,yx,y。

数据范围

1≤T≤1001\le T\le100,2≤n≤10182\le n\le10^{18}。共 20 个测试点。

测试点 附加条件
1–4 n≤1010n\le10^{10}
5–6 n=2kn=2^k
7–12 nn 是模 4 余 1 的素数
13–16 n=pkn=p^k,其中 pp 是素数
17–20 无

原题面 PDF