ztr loves math
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 766 Accepted Submission(s): 296
Problem Description ztr loves research Math.One day,He thought about the "Lower Edition" of triangle equation set.Such as n=x2−y2 .
He wanted to know that ,for a given number n,is there a positive integer solutions?
Input There are T test cases.
The first line of input contains an positive integer T(T<=106) indicating the number of test cases.
For each test case:each line contains a positive integer , n<=1018 .
Output If there be a positive integer solutions,print True ,else print False
Sample Input
4
6
25
81
105
Sample Output
False
True
True
True
Hint
For the fourth case,$105 = 13^{2}-8^{2}$
问题描述
ztr喜欢研究数学,一天,他在思考直角三角形方程组的Lower版,即n=x^{2}-y^{2}n=x2−y2,他想知道,对于给出的n,是否会有正整数解。
输入描述 有T组数据,第一行为一个正整数T(T<=10^{6})T(T<=106),每一行一个正整数n,n <=10^{18}n<=1018
输出描述 如果有正整数解,输出TrueTrue,否则输出FalseFalse
输入样例 4
6
25
81
105
输出样例 False
True
True
True
Hint 对于第四个样例,有一组解13^{2}-8^{2}=105132−82=105
//首先可以模拟一下前面的几个数: 前九个数的平方为: 1 4 9 16 25 36 49 64 81 相邻两个数的差值为: 3 5 7 9 11 13 15 17 由上面的数可以看出如果是相邻两个数的话,n的值为奇数,但也可能为偶数(比较特殊),例如: 9-1=8 16-4=12等... 除了这两种情况没有其他的情况了,所以根据这两个发现可以找出规律: if((n&1ll&&n!=1)||(n%4==0&&n!=4))
printf("True\n");
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
int main()
{
int t,i,j,k;
ll n;
scanf("%d",&t);
while(t--)
{
scanf("%lld",&n);
if((n&1ll&&n!=1)||(n%4==0&&n!=4))
printf("True\n");
else
printf("False\n");
}
return 0;
}