package main import . "fmt" import . "math/big" func main() { var n Int Scan(&n) if n.Cmp(NewInt(2)) <= 0 { Println(-1) return } if n.Bit(0) != 0 { Println(1) return } if n.Cmp(NewInt(8)) >= 0 { Println(1) } else { Println(-1) } } /* 考察 10^25はint64には収まらんらしい… A^2 - B^2 = N 因数分解すると (A + B) * (A - B) = N これからわかることは…ない Nが素数の場合に限り A - B = 1 A + B = N に一致するものがあればokか?(N=2はダメだな…) これ、Nが3以上の奇数なら任意に可能か A=ceil(N/2),B=floor(N/2) とすれば成立かな…? Nが偶数とすると AとBの偶奇は一致する必要がある A ≡ B (mod 2) AとBの偶奇が一致すると A+BもA-Bも偶数になるので A + B ≡ A - B ≡ 0 (mod 2) Nは4の倍数である必要がある AとBは偶数と仮定して A = 2 * X B = 2 * Y N = 4 * Z と置くと (A + B) * (A - B) = N 4 * (X + Y) * (X - Y) = 4 * Z (X + Y) * (X - Y) = Z と変換できる… つまり、再帰… しかし、これだとサンプル2のN=8がACできない(Z=2で-1) つまり、AとBが奇数の場合でも考える必要がある A = 2 * U + 1 B = 2 * V + 1 N = 4 * W (A + B) * (A - B) = N 4 * (U + V + 1) * (U - V) = 4 * W (U + V + 1) * (U - V) = W と変換できる U - V = 1 と仮置きすると U + V + 1 = (V + 1) + V + 1 = 2 * (V + 1) = W これはWが4以上の偶数なら成立する(つまりNは16の倍数…) やはりこれでもサンプル2のN=8はACできない… サンプル2の説明書きを参考にすると A - B = 2 となる つまり (A + B) * (A - B) = ((B + 2) + B) * 2 = 4 * (B + 1) = N これはつまりNが8以上の偶数なら成立することを意味する なお、N=4は暗算でも成立しないことがわかる */