【题解】CF1139D Steps to One

一月 28, 2021

我有一个不一样的推式子方法。

先将问题转换一下，假设当前的 gcd $x=p1^{k1}p2^{k2}\cdots$，即为求：

$E(\max(\forall i,\min(k_i)=0))$

不妨将每个质数 $p$ 看成一个物品，

假设 $x$ 是新插入集合的数，不妨将 $x$ 看成一个这样的操作：

将与 $x$ 互质的物品取走。

现在问题转化成了一个取物品的的问题，即为求：

$E(\max(S))$

那么直接 Min-max 容斥：

$E(max(S)=\sum_{T\in S}(-1)^{|T|+1}E(min(T)=\sum_{T\in S}(-1)^{|T+1|}\frac{1}{P(T)}$

考虑当 $\prod_{x\in T}x>n$ 时 $P(T)=1$，且 $x$ 为质数，于是可以将式子改写:

$E(max(S))=\sum_{T\in S}(-1)^{|T|+1}-\sum_{i=2}^n \mu(i)+\sum_{i=2}^n \mu(i)\lfloor\frac{n}{i}\rfloor=1-\sum_{i=2}^n \mu(i)+\sum_{i=2}^n \mu(i)\lfloor\frac{n}{i}\rfloor$

然后问题就解决了。

int qmod(int x,int y)
{
	int ans=1;
	while(y)
	{
		if(y&1)(ans*=x)%=M;
		(x*=x)%=M;
		y>>=1;
	}
	return ans;
}
signed main()
{
	n=read();
	int inv=qmod(n,M-2);
	for(rg int i=2;i<=n;i++)
	{
		if(!vis[i])p[++len]=i,u[i]=1;
		for(rg int j=1;j<=len&&p[j]*i<=n;j++)
		{
			vis[i*p[j]]=1;
			if(i%p[j]==0)break;
			u[i*p[j]]=-u[i];
		}
		sum=(sum-u[i]+M)%M;
	}
	for(rg int i=2;i<=n;i++)
	{
		if(u[i]==0)continue;
		mul[i]=n*qmod(n-n/i,M-2);
		sum=(sum+u[i]*mul[i]%M+M)%M;
	}
	write((sum+1)%M);
}

查看评论