问题描述
给定一个数x，求正整数y≥2，使得满足以下条件：
1.y-x的绝对值最小
2.y的质因数分解式中每个质因数均恰好出现2次。
输入描述
第一行输入一个整数T（1≤T≤50)
每组数据有一行，一个整数x（1≤x≤10^18）
输出描述
对于每组数据，输出一行y-x的最小绝对值
输入样例
5
1112
4290
8716
9957
9095
输出样例
23
65
67
244
70

代码:
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int f(int n){
    int i,k;
    if(n==1) return 1;
    for(i=2;i<=n;i++){
        k=0;
        while(n!=i){
            if(n%i==0){
                n=n/i;
                k++;
                if(k>1) return 0;
            }
            else break;
        }
    }
    return 1;
}
int main(void){
    int T,n,n1,n2;
    long long int x,y1,y2;
    scanf("%d",&T);
    while(T--){
        scanf("%lld",&x);
        n1=sqrt(x);
        n2=n1+1;
        while(!f(n1)) n1--;
        while(!f(n2)) n2++;
        y1=n1*n1;
        y2=n2*n2;
        if(n1!=1)
            printf("%lld\n",((x-y1)>(y2-x))?(y2-x):(x-y1));
        else printf("%lld\n",y2-x);
    }
}

我的思路是先把x开根号，左边整数为y1，右边为y2，判断y1，y2是不是可以分解成每个质因数只出现一次的数，不是的话分别向左右扩散，直到找到。
这个方法显示时间超限了，想问问各位大佬有没有优化的方法?

[此贴子已经被作者于2018-5-18 15:18编辑过]

其实,检测一下y1,y2是否是完全平方数就可以了,不是完全平方数则符合条件,试试看~

PS:指代错了y1,y2应该指代的是n1,n2~

[此贴子已经被作者于2018-5-18 18:47编辑过]

为什么是完全平方数?
y1，y2必须是能分解成每个质因数只出现一次的数。
比如8，它不是完全平方数，但不符合条件，因为它的质因数是2,2,2，2出现了三次。

8是指y1 y2么~
我理解错了,y1,y2应该是指n1,n2

没认真看~

我想的是开根号再比较更好，没想到还是时间超限了

但是完全平方数也不一定满足条件，比如16是完全平方数，分解质因数后是2,2,2,2，2出现了4次，也不行。每个质因数要么不出现，要么出现两次才行。

16开方是4吧~
4是完全平方数,当然不满足条件~
找些y1,y2开方后(这个代码指代的是n1,n2)不是完全平方数平方数的数就可以了~

12不是完全平方数，但是144不行，144分解质因数后是2,2,2,2,3,3，2出现了4次

算法先不说
x 是10^18
你用int就GG了

算法上
举个例子 24
最近是 25 5*5
按照你的做法 (int)根号24 == 4
4 就是 2*2满足条件
你会算出 16
所以错了
----------------------------
我理解错了 你找出现1次的
我再看看

[此贴子已经被作者于2018-5-18 21:46编辑过]