返回首页 返回专题

【BZOJ2440】完全平方数 题解

题目到底要我们求的，是因子不包含完全平方数的正整数

一个完全平方数x，必然包含了至少两个相同的质因数，也就是μ(x)=0！

那么也就是说，我们要求μ(x)≠0的数中，第n大的那一个

玄学方法可以得到答案不超过2*n，于是二分答案

二分的判断……至今没有理解……据说玄学容斥一下，然后发现容斥系数就是莫比乌斯函数……

#include<bits/stdc++.h>
using namespace std;

const int N=50000;
int mu[N+10],n;
int prime[N],tot=0;
bool mark[N+10];

void Init()
{
	memset(mark,0,sizeof(mark));
	mu[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!mark[i]) prime[++tot]=i,mu[i]=-1;
		for(int j=1;j<=tot&&i*prime[j]<=N;j++)
		{
			mark[i*prime[j]]=1;
			if(i%prime[j]) mu[i*prime[j]]=-mu[i];
			else mu[i*prime[j]]=0;
		}
	}
}

bool check(int x)
{
	int res=0;
	for(int i=1;i*i<=x;i++)
		res+=mu[i]*(x/(i*i));
	return res<n;
}

int main()
{
	Init();
	int T;cin>>T;
	while(T--)
	{
		cin>>n;
		int l=1,r=2*n;
		while(l<r)
		{
			int mid=(1ll*l+r)/2;
			if(check(mid)) l=mid+1;
			else r=mid;
		}
		cout<<l<<endl;
	}
	return 0;
}