Hdu 5778 abs （暴力_二分）

题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=5778
题目大意：
给定一个数x，求正整数$y\geq2$，使得满足以下条件：
1.$y-x$的绝对值最小
2.y的质因数分解式中每个质因数均恰好出现2次。

简单分析：
y的质因数分解式中每个质因数均恰好出现2次，显然y是个完全平方数，但不是所有的完全平方数满足每个质因数恰好出现2次，$y-x$绝对值最小的数，显然当$\sqrt{y}$在$\sqrt{x}$附近且满足条件时，绝对值最小，对$\sqrt{x}$分解质因数，若有一个因数出现2次以上，则不满足条件，减小此值，继续向下搜索，由于这样的数出现的非常频繁，所以复杂度不会爆，然后再从$\sqrt{x}+1$开始向上查找，直到找到一个满足的值，比较两次找到的数的平方与x的绝对值，最后输出小的那个
注1：第二次从$\sqrt{x}+1$开始主要是为了防止某个数x，$\sqrt{x}$满足条件，但$\sqrt{x}+1$也满足，且答案更小，
注2：由于$y\geq2$，还需要加特判当$x\leq4$时，y都只能等于4，4为最小的满足条件的y值，此时当输出$4-x$

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;

long long int x,y,temp;

bool cha(long long kai)
{
    long long int i;
    for(i=2;i*i<kai;i++)
    {
        if (kai%i==0)
	{
	    kai/=i;
	    if (kai%i==0)
	        return true;
	}
    }
    return false;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&x);
        long long kai1=(long long)sqrt(x);
        long long  kai2=kai1;
        while(cha(kai1))
        {
            kai1=kai1-1;
        }
        y=abs(kai1*kai1-x);
        kai2++;
        while(cha(kai2))
        {
            kai2=kai2+1;
        }
        y=min(y,abs(kai2*kai2-x));
        if (x<=4)
            y = 4-x;
        printf("%lld\n",abs(y));
    }
    return 0;
}