【题目描述】

给出一个x,求是否存在y和z,使得x²=y²+z²。

【输入格式】

第一行一个正整数T 表示数据组数

接下来T行 每一行一个正整数x

【输出格式】

输出T行,每一行“YES”或者“NO”,“YES”表示存在这样的正整数对(y,z),“NO”表示不存在。

注意:建议使用读入优化,不建议用cin。

【输入样例】

2

5

3

【输出样例】

YES

NO

【数据范围】

对于100%的数据 T≤1000000,n≤1000000

看到这种Orz的数据范围,一定是O(1)做法没差了。

实际上我们首先要知道费马素数定理,即一个4k+1型素数 一定能够表示成p=n²+m²的形式,然后另外有一个结论,x²=y²+z² 使得该式成立的x一定能够表示成4k+1型素数的倍数。

关于证明,呵呵,背定理吧,其实费马素数定理还是不难证明的。

所以,将1~1000000的4k+1型素数打表,然后将其倍数全部标记,查询时O(1)输出即可。

下面是代码:

 

本文为原创文章,唯一地址链接:【Vector】 转载请注明转自 stdKonjac

我来吐槽

*

*

取消

*