首页 > 代码库 > HDU 4143 A Simple Problem（数论-水题）

HDU 4143 A Simple Problem（数论-水题）

2024-07-16 22:35:42   226人阅读

A Simple Problem



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
 

Author
HIT
 

Source
2011百校联动“菜鸟杯”程序设计公开赛
 

Recommend
lcy   |   We have carefully selected several similar problems for you:  4144 4147 4145 4146 4148 
 

题目大意：

给定n，求最小的正整数x，使得 n+x^2也是完全平方数。


解题思路：

假设y^2=n+x^2 ，那么 (y-x)*(y+x)=n，也就是n的两个因子，只需枚举因子即可。


解题代码：

#include <iostream>
#include <cstdio>
using namespace std;

int n;

void solve(){
    int x=(1<<30);
    for(int i=1;i*i<=n;i++){
        if(n%i!=0) continue;
        if( (i&1) == ( (n/i)&1 ) ){
            if((n/i-i)/2>0 && (n/i-i)/2<x ) x=(n/i-i)/2;
        }
    }
    if( x<(1<<30) ) printf("%d\n",x);
    else printf("-1\n");
}

int main(){
    int t;
    scanf("%d",&t);
    while(t-- >0){
        scanf("%d",&n);
        solve();
    }
    return 0;
}






联系
我们