题意

一个正整数K被称为squarefree,如果它没有一个D^2(D>1)这样的约数。
找出第N个不是squarefree的数。1<=N<=10^10

题解

和bzoj2440是一样的题啊。。
但是由于年代悠久，我已经忘了QAQ
于是又做了一次思路
思路就是莫比乌斯搞一搞就可以了
写博客越来越不负责任了

CODE:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
const LL N=1e6;
LL T;
LL n;
bool vis[N+5];
int pri[N+5],mu[N+5],tot;
void get_mu ()
{memset(vis,true,sizeof(vis));mu[1]=1;tot=0;for (int u=2;u<=N;u++){if (vis[u]) {pri[++tot]=u;mu[u]=-1;}for (int i=1;i<=tot;i++){int j=pri[i];if (j*u>N) break;vis[j*u]=false;if (u%j!=0) mu[u*j]=mu[u]*mu[j];else {mu[u*j]=0;break;}}}
//  for  (int u=1;u<=10;u++) printf("%d ",mu[u]);
}
LL get (LL x)//有多少个 
{LL lalal=0;//有多少个 for (LL u=1;u*u<=x;u++)lalal=lalal+(x/u/u)*mu[u];lalal=x-lalal;
//  printf("%lld %lld\n",x,lalal);return lalal;
}
int main()
{get_mu();scanf("%lld",&n);LL l=1,r=100000000000;LL ans=0;while (l<=r){LL mid=(l+r)>>1;//  printf("%lld %lld %lld\n",l,r,mid);if (get(mid)>=n) {ans=mid;r=mid-1;}else l=mid+1;}printf("%lld\n",ans);return 0;
}