I SQRT
| Accept:48 | Submit:100 |
| Time Limit:1000MS | Memory Limit:65536KB |
Description
There is a positive integer N, and please give us the smallest root x of equation sqrt(N)=sqrt(x)-sqrt(y) when x and y are both positive integer.
Input
There are several test cases and end by EOF.
Each line contain a positive integer N, 1<N≤2^31-1.
Output
There is only one line for each test case.
The line contains only one integer indicate the smallest x which meet the above conditions.
Sample
Input
4
536
Sample
Output
9
1206
submit Discuss
/*
数学题，转化：n + y + 2sqrt(n*y) = x;
当 n*y 最小，则 x 整数最小
*/
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
void fan(long long n){
long long y=1,m=n;
for(int i=2;i*i<=n;i++){
int ans=0;
while(n%i==0){ ans++; n/=i; }
if(ans && (ans%2)) y*=i;
}
if(n>1) y*=n;
long long sum;
sum= m + y + (long long)sqrt(m*y*4.0);
cout<<sum<<endl;
}
int main(){
long long n;
while(cin>>n){
fan(n);
}
}