SOL：
由费马二平方和定理，解是存在且唯一的。
那么x在高斯整数意义下（在高斯整数意义下，唯一分解定理同样成立），有两个互扼的非平凡约数。a+bi 与 a-bi、
（a+bi）（a-bi）=aa+bb=x,可见a和b就是我们要求的答案。
我们找一个数k，使 x| kk+1 ，那么 x|（k+i）（k-i）
又因为gcd(a,b)=1,gcd(k,1)=1;
所以gcd（k+i，k-i）=1（这样的写法其实不严谨，我只是表示k+i与k-i互质）
gcd（a+bi，a-bi）=1
故gcd（x，k+i）=a+bi 或 a-bi
k的话，可以随机找。
高斯整数上的gcd，可以类比整数上的gcd。
#include
#define LO __int128
#define LL long long
#define pii pair
#define x first
#define y second
using namespace std;
LL qsm(LL x,LL y,LL mo){
static LL anw;
for (anw=1,x%=mo;y;y]=1,x=(LO)xx%mo) if (y1) anw=(LO)anwx%mo;
return anw;
}//代码效果参考：http://www.ezhiqi.com/zx/art_2166.html
pii operator + (pii a,pii b){
return pii(a.x+b.x,a.y+b.y);
}
pii operator - (pii a,pii b){
return pii(a.x-b.x,a.y-b.y);
}
pii operator (pii a,pii b){
return pii(a.xb.x-a.yb.y,a.xb.y+a.yb.x);
}
pii operator % (pii a,pii b){
LO fm=LO(b.x)b.x+LO(b.y)b.y;
LO aa=LO(a.x)b.x+LO(a.y)b.y;
LO bb=-LO(a.x)b.y+LO(a.y)b.x;
return a-pii(llround(aa/(long double)fm),llround(bb/(long double)fm))b;
}
pii gcd(pii a,pii b){
if (b.x==0b.y==0) return a;
return gcd(b,a%b);
}//代码效果参考：http://www.ezhiqi.com/bx/art_3235.html
int T; LL x,p,k; pii L;
int rand(){
static int X=23333; return X^=X[5,X^=X]17,X^=X[13;
}
signed main () {
scanf("%d",T);
while (T--) {
scanf("%lld",x);
while (1) {
p=rand()%(x-2)+2;
if (qsm(p,x-11,x)==x-1){
k=qsm(p,x-12,x);
break;
}
}
L=gcd(pii(x,0),pii(k,1));
L.x=abs(L.x),L.y=abs(L.y);
if (L.x>L.y) swap(L.x,L.y);
printf("%lld %lld\n",L.x,L.y);
} return 0;
}//代码效果参考：http://www.ezhiqi.com/bx/art_2637.html
