题意简述

给定 $T$ 个质数 $x \equiv 1 \pmod{4}$，要求构造非负整数 $a \le b$ 使得：

x

a 2 + b 2 x=a 2 +b 2

保证 $x$ 是满足 $x \equiv 1 \pmod{4}$ 的质数。

理论基础

根据 Fermat 定理：奇质数 $p$ 能表示成两个平方数之和当且仅当 $p \equiv 1 \pmod{4}$。 题目已经保证 $x \equiv 1 \pmod{4}$ 且是质数，所以一定有解。

构造方法

已知 $x \equiv 1 \pmod{4}$，我们可以用以下方法构造：

找到一个 $c$ 使得 $c^2 \equiv -1 \pmod{x}$，即 $c^2 + 1 \equiv 0 \pmod{x}$。

用 辗转相除法 将 $x$ 和 $c$ 进行欧几里得算法，直到余数 $r \le \sqrt{x}$，此时 $r$ 和下一个余数 $s$ 满足 $r^2 + s^2 = x$。

具体步骤

随机选取 $t \in [2, x-2]$，计算 $c \equiv t^{(x-1)/4} \pmod{x}$，检查 $c^2 \equiv -1 \pmod{x}$ 是否成立，若不成立则换 $t$。

对 $(x, c)$ 做欧几里得算法： 设 $r_0 = x, r_1 = c$，做带余除法：

r i − 1

q i r i + r i + 1 r i−1 ​ =q i ​ r i ​ +r i+1 ​

直到 $r_k \le \sqrt{x}$，则 $a = r_k, b = r_{k+1}$ 满足 $a^2 + b^2 = x$。

时间复杂度

找 $c$ 用快速幂 $O(\log x)$。

欧几里得算法 $O(\log x)$。

总体 $O(\log x)$ 每组数据。

示例代码（框架）

cpp #include <bits/stdc++.h> using namespace std; using ll = long long; using i128 = __int128_t;

ll mod_mul(ll a, ll b, ll mod) { return (i128)a * b % mod; }

ll mod_pow(ll a, ll b, ll mod) { ll res = 1; while (b) { if (b & 1) res = mod_mul(res, a, mod); a = mod_mul(a, a, mod); b >>= 1; } return res; }

// 找 c 满足 c^2 ≡ -1 (mod p) ll find_c(ll p) { ll a = 2; while (1) { ll c = mod_pow(a, (p-1)/4, p); if (mod_mul(c, c, p) == p-1) return c; a++; } }

void solve(ll p) { ll c = find_c(p); ll r0 = p, r1 = c; while (r1 * r1 > p) { ll r2 = r0 % r1; r0 = r1; r1 = r2; } ll a = r1; ll b = (ll)sqrt(p - a*a); if (a > b) swap(a, b); cout << a << " " << b << "\n"; }

int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { ll x; cin >> x; solve(x); } return 0; }

总结

利用 $x \equiv 1 \pmod{4}$ 质数的二平方和定理。

随机或顺序找 $c$ 满足 $c^2 \equiv -1 \pmod{x}$。

用欧几里得算法得到 $a, b$。

注意大数乘法用 __int128 避免溢出。