P9865 [POI2021~2022R2] lic 题解

· · 题解

题目传送门

题目简意：

给定正整数 n，将所有与 n 互质（包括 1）的正整数按照升序排列，并输出第 k∼k+c-1 个正整数。

分析：

首先我们要知道那些数字是和 n 不互质的，那么筛去这些数，剩下的就是满足条件的。首先 n 的因子（1 除外）和 n 都是不互质的，并且当一个数是 n 的因子的倍数时，它和 n 也不互质。那么我们可以找到 n 的所有质因子，然后把这些质因子的所有倍数筛去，剩下的就是我们要找的。

接下来考虑筛法，我们可以用 O(\sqrt{n}) 的复杂度找到 n 的所有质因子。但是接下来扩张倍数就是个问题，因为直接 O(n) 扩张会超时，假设第 k 位的数字为 x，那么考虑能不能算出来 1∼x 之间有多少个要筛去的，记做 res，那么用 x-res 就是所求得到结果。我们会发现如果 n 只有一个因子，那么 x-res，而当因子大于 1 时，肯定会筛重复的，考虑容斥原理。

记 n 的因子为 p_{1}，p_{3}\cdots p_{m}，现在抽象出几个集合，每个集合的元素个数就是 \lfloor \frac{x}{p_{1}}\rfloor，\lfloor \frac{x}{p_{2}}\rfloor\cdots\lfloor \frac{x}{p_{m}}\rfloor，那么我们要求的是这几个集合的并集的元素个数，根据容斥原理：

|A_{1}\cup A_{2} \cup \cdots\cup A_{m}| =\displaystyle\sum_{1\le i\le m}|A_{i}|-\displaystyle\sum_{1\le i< j\le m}|A_{i}\cap A_{j}|+\displaystyle\sum_{1\le i< j< k\le m}|A_{i}\cap A_{j}\cap A_{k}| -\cdots +(-1)^{m-1}|A_{1}\cap A_{2}\cap\cdots\cap A_{m}|

此时，我们已经解决了当第 k 位的数字为 x，筛去的个数为 res，但是这里 x 是未知的，我们考虑 x 与 k 之间的关系：

res=\displaystyle\sum_{1\le i\le m}\lfloor \frac{x}{p_{i}}\rfloor\displaystyle\sum_{1\le i< j\le m}\lfloor \frac{x}{p_{i}\cdot p_{j}}\rfloor+\displaystyle\sum_{1\le i< j< k\le m}\lfloor \frac{x}{p_{i}\cdot p_{j}\cdot p_{k}}\rfloor -\cdots +(-1)^{m-1}\lfloor \frac{x}{p_{i}\cdot p_{j}\cdots p_{m}}\rfloor x-res=k

考虑构造函数 f(x)=x-res-k，容易证明这个函数是单调不减的，那么可以用二分法来确定 x，但由于单调不减，所以最后二分出来的两个端点 l 和 r 都有可能，只需要在判断一下就好了。

现在知道了第 k 位上的数 x 是多少，那么怎么求 k∼k+c-1 上的每个数是多少呢。这里有两种办法：

  1. 是对于每个点都进行二分，得到结果 i，这只适合每个 i 比较稀疏的分布。

  2. 从第 k 位的 x 开始往后找，每次一个数 i 判断 \gcd(i,n) 是否等于 1，是的话输出，输出 c 位后结束循环，适合每个 i 比较稠密的分布。

事实证明，此题解法 2 能通过，以下是评测记录：

解法1

解法2

代码实现

#include<bits/stdc++.h>
#define int long long//记得开long long
using namespace std;
int n,k,c,l,r,meici;
int a[1111],cnt;//a数组存储质因子
bool pd;

void dfs(int x,int y,int dep,int ceshi)//递归求解容斥，x表示循环到第几层，y表示上一轮第几个质数参与运算，dep表示每一项的分母是多少，ceshi表示分子是多少
{
    if(x==0)
    {
        meici+=ceshi/dep;
        return;
    }
    for(int i=y+1;i<=cnt;i++)
    {
        dfs(x-1,i,dep*a[i],ceshi);
    }
}

int judge(int x)//求解res
{
    int res=0;
    for(int i=1;i<=cnt;i++)
    {
        meici=0;
        dfs(i,0,1,x);
        if(i&1) res+=meici;
        else res-=meici;
    }
    res=x-res;
    res-=k;
    return res;
}

bool pdd(int x)//判断是否合法
{
    for(int i=1;i<=cnt;i++) 
    {
        if(x%a[i]==0)
        {
            return false;
        }
    }
    return true;
}

int work(int x)//朴素二分
{
    l=1;
    r=1e18;
    while(l<=r)
    {
        int mid=(l+r)>>1;
        int op=judge(mid);
        if(op>=0) r=mid-1;
        else l=mid+1;
    }
    if(pdd(l)&&judge(l)>=0) return l;//判断取l还是r
    else return r;
}

int gcd(int x,int y)
{
    if(y==0) return x;
    return gcd(y,x%y);
}

signed main()
{
    scanf("%lld%lld%lld",&n,&k,&c);
    int nn=n;
    for(int i=2;i*i<=n;i++)//拆质数
    {
        if(n%i==0)
        {
            a[++cnt]=i;
            while(n%i==0) n/=i;
        }
    }
    if(n>1) a[++cnt]=n;
    int st=work(k);
    for(int i=st;;i++)
    {
        if(gcd(i,nn)==1)
        {
            printf("%lld ",i);
            c--;
        }
        if(c<=0) break;
    }
    return 0;
}