分析:y是一个无平方因子数的平方,所以可以从sqrt(x)向上向下枚举找到第一个无平方因子比较大小

大家可能觉得这样找过去暴力,但实际上无平方因子的分布式非常密集的,相关题目,可以参考

CDOJ:无平方因子数 http://acm.uestc.edu.cn/#/problem/show/618

这个题和CDOJ的题虽然不一样,但是可以从CDOJ发现这种数是很多的

官方题解:官方题解说这个无平方因子的枚举量在logn级别,可见非常小

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <vector>
using namespace std;
typedef long long LL;
const int N = 1e5+;
bool v[N];
int prime[N>>],cnt;
void getprime(){
for(int i=;i*i<=N-;++i)
if(!v[i])
for(int j=i*i;j<=N-;j+=i)
v[j]=;
for(int i=;i<=N-;++i)
if(!v[i])prime[++cnt]=i;
}
LL fun(LL x,LL y){
if(x>y)swap(x,y);
return y-x;
}
int main(){
int T;
getprime();
scanf("%d",&T);
while(T--){
LL n;scanf("%I64d",&n);
LL x=(LL)(sqrt(1.0*n)+0.5),l=-,r=-;
for(int k=x;k>=;--k){
bool flag=false;
for(int i=;i<=cnt&&1ll*prime[i]*prime[i]<=k;++i){
if(k%(1ll*prime[i]*prime[i])==){flag=true;break;}
}
if(!flag){l=k;break;}
}
for(int k=x+;;++k){
bool flag=false;
for(int i=;i<=cnt&&1ll*prime[i]*prime[i]<=k;++i){
if(k%(1ll*prime[i]*prime[i])==){flag=true;break;} }if(!flag){r=k;break;}
}
LL ret;
if(l==-)ret=fun(r*r,n);
else ret=min(fun(n,l*l),fun(r*r,n));
printf("%I64d\n",ret);
}
return ;
}
04-27 03:40