ztr loves math

题目链接：

http://acm.hust.edu.cn/vjudge/contest/123316#problem/A

Description

ztr loves research Math.One day,He thought about the "Lower Edition" of triangle equation set.Such as n = x^2 - y^2.

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 indicating the number of test cases.

For each test case:each line contains a positive integer ,.

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-82.

题意：

给出一个N(N<=10^18);

问N能否由两个完全平方数相减得到;

题解：

对于相邻自然数 n 和 n+1 ：

(n+1)^2 - n^2 = 2n+1;

即相邻两平方数之差一定是一个奇数；

那么任意两个平方数之差一定是多个连续奇数的和.

而任意两个连续奇数之和为：

(2n-1) + (2n+1) = 4n;

即两个连续奇数之和必定能整除4；

那么本题满足条件的n须两个性质之一：

N为奇数
N能被4整除；

特判：由于题目要求任一平方数不能为0；

则1和4不满足要求.

TLE了一发：把puts和cin都换掉就过了...

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>

#include <map>

#include <set>

#include <vector>

#define LL long long

#define eps 1e-8

#define maxn 1100

#define inf 0x3f3f3f3f

#define IN freopen("in.txt","r",stdin);

using namespace std;

LL n;

int main(int argc, char const *argv[])

{

    //IN;

    int t;  scanf("%d", &t);

    while(t--)

    {

        scanf("%I64d", &n);

        if(n == 1 || n==4) {

            printf("False\n");

            continue;

        }

        if(n&1 || n%4==0) printf("True\n");

        else printf("False\n");

    }

    return 0;

}

秒客网

HDU 5675 ztr loves math （数学推导）