NKOJ3959 天真的因数分解（二分答案+容斥原理+莫比乌斯函数）

发表于 |
字数统计: 764字 | 阅读时长 ≈ 3min
问题描述

小岛: 什么叫做因数分解呢?

doc : 就是将给定的正整数n, 分解为若干个素数连乘的形式.

小岛: 那比如说 n=12 呢?

doc : 那么就是 12 = 2 X 2 X 3 呀.

小岛: 呜呜, 好难, 居然素数会重复出现, 如果分解后每一个素数都只出现一次, 我就会.

wish: 这样来说, 小岛可以正确分解的数字不多呀.

doc : 是呀是呀.

wish: 现在问题来了, 对于给定的k, 第 k 个小岛无法正确分解的数字是多少?

输入格式

输入只有一行, 只有一个整数 k.

输出格式

输出只有一行, 只有一个整数, 表示小岛无法正确分解出来的第k个数字.

样例输入 1

10

样例输出 1

27

样例输入 2

23

样例输出 2

60

提示

对于30%的数据, k <= 2,000,000

对于100%的数据, 1 <= k <= 10,000,000,000

​ 首先，设要求的第K个无法正确分解的数为$A_k$，显然是没有关于k的式子可以直接推出$A_k$，所以考虑二分答案。

​ 枚举一个数X，现在问题变成求1~X有多少个无法正确分解的数。

​ 考虑一个无法正确分解的数M，那么将M标准分解后，肯定存在一个素因子P，且P的次数≥2。

​ 那么 $\frac{x}{p^2}$ 显然表示了 $1-X$ 中包含 $p^2$ 的数的个数，因此枚举 $p$ 累加，但显然加重了，所以这里用容斥原理处理一下得到

$$
Ans=\frac{X}{p_1^2}-\frac{X}{(p_1p_2)^2}+\frac{X}{(p_1p_2p_3)^2}\cdots
$$
​ 最后，观察一下系数，联想莫比乌斯函数，可以发现每一项前的系数就是分母内的数的莫比乌斯函数的相反数，并且分母的最大值显然是 $\sqrt{X}$，得到最后的求和式：

$$
Ans=\sum_{i=1}^{\sqrt{X}}-\mu(i)\frac{X}{i^2}
$$
​ 用线性筛预处理一下，至于二分的上限可以目测一下，我取的100*k，至此可以在 $O(\log{(ck)}\sqrt{ck}+\sqrt{ck})$ 的时间复杂度内解决该问题。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ll long long
#define N 12345678
using namespace std;
ll k,n,p[N],tot;
short mu[N];
bool mark[N];
void EU()
{
	ll i,j,x=sqrt(n);
	mu[1]=1;
	for(i=2;i<=x;i++)
	{
		if(!mark[i])p[++tot]=i,mu[i]=-1;
		for(j=1;j<=tot&&p[j]*i<=x;j++)
		if(i%p[j])mark[i*p[j]]=1,mu[i*p[j]]=-mu[i];
		else mark[i*p[j]]=1,mu[i*p[j]]=0;
	}
}
bool ok(ll x)
{
	ll i,y=sqrt(x),sum=0;
	for(i=2;i<=y;i++)sum+=-mu[i]*(x/(i*i));
	if(sum>=k)return 0;
	return 1;
}
ll EF(ll l,ll r)
{
	while(l<=r)
	{
		ll mid=l+r>>1;
		if(ok(mid))l=mid+1;
		else r=mid-1;
	}
	return l;
}
int main()
{
	scanf("%lld",&k);
	n=100*k;
	EU();
	cout<<EF(1,n);
}