记录编号	477715	评测结果	AAAAAAAAAA
题目名称	[vijos1889]天真的因数分解	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	0.458 s
提交时间	2017-12-06 15:53:45	内存使用	6.04 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define N 500010
#define LL long long
LL k;
int mu[N],notprime[N],prime[N];
void getmu(){
	mu[1]=1;notprime[1]=1;
	pos(i,2,N-10){
		if(!notprime[i]){
			mu[i]=-1;
			prime[++prime[0]]=i;
		}
		for(int j=1;j<=prime[0]&&prime[j]*i<=N-10;j++){
			notprime[i*prime[j]]=1;
			if(i%prime[j]==0){
				mu[i*prime[j]]=0;break;
			}
			mu[i*prime[j]]=-mu[i];
		}
	}
}
LL l,r;
LL tot(LL x){
	LL top=(LL)sqrt(x);
	LL sum(0);
	for(LL i=1;i<=top;i++){
		sum+=x/(i*i)*mu[i];
	}
	return sum;
}
int main(){
	freopen("naive.in","r",stdin);
	freopen("naive.out","w",stdout);
	scanf("%lld",&k);
	getmu();
	l=k;r=(LL)1e11;
	while(l<=r){
		LL mid=(l+r)>>1;
		if(mid-tot(mid)<k) l=mid+1;
		else r=mid-1;
	}
	cout<<l;
	return 0;
}