• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

P4318 完全平方数

开发技术 开发技术 1周前 (06-08) 11次浏览

完全平方数

求第 (k) 个无平方因子的数,(kleq 10^9)

考虑二分答案,问题变为求 (1sim n) 中无平方因子数的个数。

然后考虑容斥,枚举平方因子,设 (F(i)=n/i^2),那么有:

[Ans=n-F(A)+F(B)-F(C)cdots
]

其中 (A) 表示有 (1) 个因子的数的集合,(B) 表示有 (2) 个不同因子的数的集合,依此类推。

然后不难发现,每个数前面对应的系数,恰好是 (mu(i)),这样就省去了容斥的 (O(n^3))

时间复杂度为 (O(sqrt Nlog N))(N) 为二分值域。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long LL;
const LL INF = 0x7fffffff;
const int N = 1e6 + 10;
int T, n, tot, mu[N], prm[N];
bool vis[N];

int read(){
	int x = 0, f = 1; char c = getchar();
	while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
	return x * f;
}

void Get_Mu(){
	mu[1] = 1;
	for(int i = 2; i <= N - 10; i ++){
		if(!vis[i])
			prm[++ tot] = i, mu[i] = -1;
		for(int j = 1, num; j <= tot && (num = prm[j] * i) <= N - 10; j ++){
			vis[num] = true;
			if(i % prm[j]) mu[num] = - mu[i];
			else{
				mu[num] = 0;
				break;
			}
		}
	}
}

bool chck(LL mid){
	LL sum = 0;
	for(int i = 1; i * i <= mid; i ++)
		sum += 1LL * mu[i] * (mid / (i * i));
	return sum >= n;
}

int main(){
	Get_Mu();
	T = read();
	while(T --){
		n = read();
		LL l = 1, r = INF;
		while(l < r){
			LL mid = (l + r) >> 1;
			if(chck(mid)) r = mid;
			else l = mid + 1;
		}
		printf("%lldn", l);
	}
	return 0;
}

程序员灯塔
转载请注明原文链接:P4318 完全平方数
喜欢 (0)