首页 > 代码库 > A Simple Problem

A Simple Problem

2024-07-03 04:39:52   235人阅读

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;
}


联系
我们