自动搬运

查看原文

来自洛谷，原作者为

	bianshiyang 乌云过后仍会是漫天星辰

搬运于2025-08-24 22:52:32，当前版本为作者最后更新于2023-12-07 18:34:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

题目简意：

给定正整数 $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;
}