Google 一下就好了~
还是 Google 一下就找到了.
An integer greater than one can be written as a sum of two squares if and only if its prime decomposition contains no prime congruent to 3 modulo 4 raised to an odd power.
根据 Brahmagupta–Fibonacci identity, 先试图分解给定整数, 直到满足条件.
再利用 Gaussian GCD 计算每个质数的分解.