绝对值（HG 2018.5.13 T1）
hicc0305
2018-05-13 18:54:54
### 【问题描述】
给定一个数 x，求正整数 y≥2，使得满足以下条件：
1.y-x 的绝对值最小；
2.y 的质因数分解式中每个质因数均恰好出现 2 次。
### 【输入数据】
第一行输入一个整数 T(1≤T≤50)
每组数据有一行，一个整数 x(1≤x≤10^18)
【输出数据】
对于每组数据，输出一行 y-x 的最小绝对值。
### 【输入样例 1】
5
1112
4290
8716
9957
9095
### 【输出样例 1】
23
65
67
244
70
### 【数据范围】
对于 20% 的数据, T = 1, x ⩽ 10^4
对于 50% 的数据, T ⩽ 10, x ⩽ 10^12
对于 70% 的数据, T ⩽ 30, x ⩽ 10^15
对于 100% 的数据, T ⩽ 50, x ⩽ 10^18
### 【题目来源】
HDU5778
因为每个质因数恰好出现 2 次,所以 y 必定是一个完全平方数
假设 y=z*z
那么 z 必定是一个由不同质数构成,且每种质数仅有一个的 10^9 以内的整数
对于一个 10^9 范围内的数,若它在sqrt(10^9)之内没有找到因子的话,那这个数必定是一个质数
显然,z 为质数时也是满足的。
那么我们就从 sqrt(x)开始,分别向下,向上枚举,直到找到符合题意的 z,哪个|y-x|小就取哪个
特判 x<4 的情况,因为题目规定 y>=2
代码如下：
```cpp
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
long long read()
{
long long x=0,flag=0;
char ch=getchar();
if(ch=='-') flag=1;
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x*=10,x+=ch-'0',ch=getchar();
if(flag) return -x;
return x;
}
bool can(long long x)//判断x是否满足质因数分解后每个质因数恰好出现一次
{
for(long long i=2;i*i<=x;i++)
{
if(x%i==0)
{
int num=0;
while(x%i==0)
{
x/=i;
num++;
if(num>1) return 0;
}
}
}
return 1;
}
int T;
int main()
{
freopen("abs.in","r",stdin);
freopen("abs.out","w",stdout);
T=read();
while(T--)
{
long long a=read();
long long b=sqrt(a);
long long i,j;
if(a<=4)
{
cout<<4-a<<endl;
continue;
}
for(i=b+1;i<=10000000000;i++)//i=b是不行的，因为有可能在i=b的的时候就弹出，而当i=b+1是实际上也可以并且答案更小
if(can(i)) break;//向上枚举
for(j=b;j>=2;j--)
if(can(j)) break;//向下枚举
printf("%lld\n",min(abs(i*i-a),abs(a-j*j)));
}
fclose(stdin);
fclose(stdout);
return 0;
}
```