题解：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。

代码详解

#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;
}