HDU 5778 abs (BestCoder Round #85 C)素数筛+暴力

分析：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 ;

}