マスター・オブ・整数で競技プログラミングその３つづき

問題

$入力：自然数N$

$出力：A ^ 2 + B ^ 2 + G ^ 2 + L ^2 = Nを満たすA，B（A \gt B）の組の総数。$

$ただし，A，Bは自然数，G，LはそれぞれA，Bの最大公約数と最小公倍数$

解説

$A = A' G, B = B'G$ と書き直すと $A', B'$ は互いに素。また， $AB = GL$ 。これらを $A ^ 2 + B ^ 2 + G ^ 2 + L ^2 = N$ に代入して整理すると $(A' ^ 2 +1)(B' ^2 + 1) G^ 2 = N$

ここで $N$ の素因数分解を考える。

$N$ が素数のとき

$A' ^ 2 + 1 = N, B' ^ 2 + 1 = 1, G = 1$ のときのみ条件を満たすが， $A, B$ は自然数より条件を満たすような $A, B$ は存在しない。
$N = p _1 ^ {a_ 1} \cdot p _2 ^ {a_ 2} \cdot \cdots \cdot p _n ^ {a_ n}$ のとき
- すべての $i についてa _i = 1$ のとき
  $G = 1$ ，つまり， $A, B$ は互いに素となり， $A = A', B = B'$ なので，満たすべき条件式は $(A ^ 2 +1)(B ^2 + 1) = N$ である。 $N$ の素因数分解がわかっているので， $N = P \times Q ( P > Q)$ の形に因数分解して，条件式を満たすかどうか全探索すれば良い。
- ある $k についてa _k \geq 2$ のとき
  $G = a _k$ とすれば， $N' = \frac{N}{a ^2 _ k}$ として， $(A' ^ 2 +1)(B' ^2 + 1) = N'$ を満たす $A' , B'$ を $N'$ の素因数分解を元にして全探索すればよい。
- 結局全探索するので，上記の $G=1$ と $G \neq 1$ の場合分けは無くても良い。また， $N$ の素因数分解を考える代わりに， $N$ の約数を列挙している（どうせ $A', B'$ で約数を用いることになる）。

#Nの約数を取得
def make_divisors(n):
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
#平方数かどうか
def isSquare(n):
    if n < 0:
        return False
    if (n**0.5).is_integer():
        return True
    else:
        return False
#最大公約数を取得
def gcd(a,b):
    if b == 0:
        return a
    return gcd(b,a%b)
#互いに素かどうか
def isCoPrime(a,b):
    if gcd(a,b) == 1:
        return True
    else:
        return False

N = int(input())
N0 = N
divisors = []
make_divisors(N)
#Nが素数の場合
if len(divisors) == 2:
    print("No ans")
    exit()
for g in divisors:
    N = N0
    if not g**2 in divisors:
        continue
    else:
        N //= (g**2)
    for d in divisors:
        d /= g**2
        dd = N//d
        if 1 in (d,dd):
            continue
        elif d >= dd:
            if isSquare(d-1) and isSquare(dd-1) and isCoPrime(int(d**0.5),int(dd**0.5)):
                print(int(d**0.5)*g,int(dd**0.5)*g)