题解：P9865 [POI 2021/2022 R2] lic

P9865 [POI 2021/2022 R2] lic

题目大意

对于一个正整数

n

，将所有与

n

互质的数从小到大排列，求此列表中的第

k∼k+c−1

个数。

思路描述

本质上，想要完成题目的要求，求出在

k

后的

c

个与

n

互质的自然数，其实只需要反过来，求出范围内不和

n

互质的数（即和

n

的最大公约数大于

1

）的集合，在该集合外的，就是我们要求的。

Part 1

因此第一步十分寻常，在

\sqrt{n}

的时间复杂度下求出 $n$ 的质因数，存起来（后文统一为该数组命名为

P

，并将

P

的长度命名为

len

）。

接下来，我们又惊喜地发现：长度

c

的范围为：

1 ≤ c ≤ 100000

！想想就知道，与

n

互质的数排列一定不会十分稀疏，因此只需要找到答案的开头（即序列中的第

k

个），然后从它开始暴力枚举出接下来的 $c$ 个即可。

而如果只想找到开头，就不难想到：二分答案。

那么重点就在于：如何写 check 函数。

Part 2

这一部分的写法可能有点抽象，需要用到位运算，如果对这方面的知识有疑问，详情可见这里。

直接讲思路，简单说就是：我们需要对于每个自然数 $x$ ，检查它是否包含了 $k$ 个及以上的与 $n$ 互质的数，如果是，则二分中的

r

减小，否则

l

增大。

进一步，要想得到答案，刚才处理好的

P

数组就有用了，但因为该数组里的因数在范围内大概率有重复，因此整个问题就变成了容斥原理——即处理 $n$ 的质因数数组中的元素的倍数的交集，因此需要使用集合，如果对这方面不清楚，可以看这里。

那么如何高效地对一个集合进行操作呢？此处提供一个十分具有启发性的方法，有点像状压：这里，此处就只讲一下和本题有关的关键点：

我们可以对

P

数组枚举每个因数的组合，因此参考刚才链接中的方法，枚举所有的状态 $plans$ （表示为整形变量，转化为二进制后对于从低往高的第

i

位，该位为

1

则表示要选择因数

Pi

，否则不选，因此枚举

plans

的最大取值不到

2^{len}

，因为选择的

P

数组长度仅有

len

，则

plans

最大时二进制下每一位都为

1

，即

2^{len}-1

）。而我们在每次枚举中要做的，就是读取 $plans$ 二进制下的每一位，并记录一个临时乘积 $now$ ，表示为若干个 $Pi$ 相乘。

那么，

plans

有了，方案乘积

now

如何记录呢？或者从根本上说，怎么高效读取

plans

从低往高的第

i

位呢？其实很简单，再暴力枚举一个需要查看的

i

（从

0

到

len-1

），考虑进行位运算：

读取

plans

从低往高的第

i

位分两步：先砍掉

plans

的后

i-1

位（

plans

右移

i

位），再取剩下的数的最后一位（与

1

进行与运算）——总的来说：plans>>i&1就是我们求的。接下来，若取到的值为

1

，

now

乘上

Pi

即可。

而每次枚举

plans

的最后，我们则需要维护一个

cnt

，记录当前被检查的数 $x$ 包含了多少个与 $n$ 互质的数，由于当前枚举的数为

now

，因此它在 $x$ 范围中出现了 $\lfloor\frac{x}{now}\rfloor$ 次，可是就像我们前面提到过的，

x

当中大概率有不止一个数为

now

的

k

倍，因此需要考虑容斥，算出当前的

now

在答案中的贡献为正或是为负即可。

那么具体考虑一下，不难想到，若我们需要计算所有

now

的并集，则当取了奇数个

Pi

时，对于答案的贡献就一定为正，否则说明该集合为某两个集合的交集，贡献为负。而我们现在要求与

n

互质的数的集合，因此该集合为刚才的集合的补集，所以应反过来：当取了奇数个 $Pi$ 时，对于答案的贡献为负，否则贡献为正。详如图解：

（实现中可以在计算 $now$ 时统计 $cnt$ ，也可以使用 GCC 自带的 __builtin_parity 函数统计 $plans$ 二进制下 $1$ 的个数的奇偶性）

因此， $cnt$ 每次应加上： $\lfloor\frac{x}{now}\rfloor \cdot \begin{cases} -1 & x \in \mathbb O \\ 1 & x \in \mathbb E \\ \end{cases} (x,now \in \mathbb N^+)$ 。

Part 3

最后，按我们之前设想的，通过__gcd函数从二分的答案开始枚举出 $c$ 个，然后输出，代码记得开 long long。

代码详解

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,k,c,t,l,r;
vector<int> p,ans;
bool check(int x){
	int cnt=0,now;
    //blk同刚才讲的plans
	for(int blk=0;blk<(1<<t);blk++){
		now=1;
        //计算被选中的Pi乘积now
		for(int i=0;i<t;i++)
			if(blk>>i&1) now*=p[i];
        //集合计算
		cnt+=(x/now)*(__builtin_parity(blk)?-1:1);
	}
    //check返回
	return cnt>=k;
}
signed main(){
	freopen("prime.in","r",stdin);
	freopen("prime.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>k>>c;
    //预处理质因数P
	int now=n;
	for(int i=2;i*i<=now;i++)
		if(now%i==0){
			p.push_back(i);
			while(!(now%i)) now/=i;
		}
	if(now!=1) p.push_back(now);
    //二分答案
	t=p.size(),l=0,r=1e18;
	while(l+1<r){
		int mid=(l+r)/2;
		if(check(mid)) r=mid;
		else l=mid;
	}
	now=r;
    //从r枚举出所有答案
	while(ans.size()<c){
		if(__gcd(now,n)==1) ans.push_back(now);
		now++;
	}
	for(int i=0;i<c;i++) cout<<ans[i]<<" ";
	return 0;
}

题解：P9865 [POI 2021/2022 R2] lic

文章操作

P9865 [POI 2021/2022 R2] lic

题目大意

思路描述

Part 1

Part 2

Part 3

代码详解

相关推荐

评论

题解：P9865 [POI 2021/2022 R2] lic