首页 > 代码库 > 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).
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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。