A Simple Problem

2
2
3

-1
1

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

HDU 4143 A Simple Problem（数论-水题）,布布扣,bubuko.com

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

原文：http://blog.csdn.net/a1061747415/article/details/38492327