首页 > 代码库 > A Simple Problem

A Simple Problem

Description

For a given positive integer n, please find the smallest positive integer x that we can find an integer y such that y^2 = n +x^2.
 

Input

The first line is an integer T, which is the the number of cases.
Then T line followed each containing an integer n (1<=n <= 10^9).
 

Output

For each integer n, please print output the x in a single line, if x does not exit , print -1 instead.
 

Sample Input

2 2 3
 

Sample Output

-1 1
题意是求最小的X;
解:用简单的暴力求解必然超时,10^9,;
因 :y^2 = n +x^2 ,y^2 - x^2 = n; (y-x)(y+x) = n;
满足条件的示例有: 3^2 = 5 + 2^2;
8^2 = 39 + 5^2;
(5^2 = 24 + 1^2;)/(7^2 = 24 + 5^2).......
明显可以看出 n = R(x+y);R是常数; 5 = 1(3+2),39 = 3(8+5),24 = 4(1+5),24 = 2(7+5).。。。。
故:
x = (n/R-R)/2;y = (n/R+R)/2;
然后进行枚举R,即可AC;
296KB 140ms
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
int main()
{
    int t,n;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        long long int R;
        int flag = 0;
       for(R=(int)sqrt(n);R>=1;R--)
       {//if里面的条件,要自己进行一些调试工作
         if((n/R-R)%2==0&& (n%R)==0 &&(n/R-R)/2!=0&& n!=R*R)
         {
            printf("%lld\n",(n/R-R)/2);
            flag=1;
            break;
         }
       }
          if(!flag)
            printf("-1\n");

    }
    return 0;
}