给定整数n决定是否有可能重新present它作为整数的两个平方的总和 [英] Given integer n decide if it is possible to represent it as a sum of two squares of integers

问题描述

输入规格：

  输入

第一行包含一个整数 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!

这篇关于给定整数n决定是否有可能重新present它作为整数的两个平方的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！