给定整数n决定是否有可能重新present它作为整数的两个平方的总和

本文介绍了给定整数n决定是否有可能重新present它作为整数的两个平方的总和的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 输入规格：  输入

第一行包含一个整数 T＆LT; = 10000 ：测试用例数目。  ŧ线跟随，他们每个人包括只有一个整数 0℃; = N＆LT; = 10 ^ 8

输出规格：  

对于每个测试用例输出是是否有可能重新present给定数目为两个平方的总和和否如果它是不可能的。

解决方案

提示：一些N是前pressible为2格当且仅当的总和N的素因子分解时，表单（4K + 3）的每一个素数发生偶数次！

INPUT SPECIFICATION:

First line of input contains one integer t <= 10000: number of test cases. T lines follow, each of them consisting of exactly one integer 0 <= n <= 10^8.

OUTPUT SPECIFICATION:

For each test case output Yes if it is possible to represent given number as a sum of two squares and No if it is not possible.

解决方案

Hint: A number N is expressible as a sum of 2 squares iff in the prime factorization of N, every prime of the form (4k+3) occurs an even number of times!