Problem Description Given a number x, ask positive integer y≥2, that satisfy the following conditions: 1. The absolute value of y - x is minimal 2. To prime factors decomposition of Y, every element factor appears two times exactly.
Input The first line of input is an integer T ( 1≤T≤50) For each test case，the single line contains, an integer x ( 1≤x≤1018)
Output For each testcase print the absolute value of y - x
Sample Input 5 1112 4290 8716 9957 9095
Sample Output 23 65 67 244 70
思路：每个素数出现两次，首先想到开根号。开完根号以后，暴力枚举离开过根号距离近的整数（先是本身），看是否符合每个素数只出现一次。
#include<iostream> #include<stdlib.h> #include<algorithm> #include<cmath> using namespace std; long long ans; #define inf 1111111111111 long long x; bool solve(long long f) { if(f<2) return false; long long t=f; for(long long i=2;i*i<=t;i++) { if(t%i==0) { if(t%(i*i)==0)//只能有一个素数 return false; t/=i; } } ans=min(ans,abs(f*f-x)); return true; } int main() { int n; cin>>n; while(n--) { cin>>x; long long t=(long long)(sqrt(x)+0.5);//寻找离开过根号最近的点，如小数部分比0.5大应该进一。 int ok=0; ans=inf; for(int i=0; ;i++) { if(solve(t+i)) { ok=1; } if(solve(t-i)) { ok=1; } if(ok==1) break;//左右都进行过查找，再退出。 } cout<<ans<<endl; } return 0; }