题目

题目链接：https://codeforces.com/problemset/problem/585/E
有一个包含 \(n\) 个 \(\in [2, 10^7]\) 的整数的可重集合。
要求满足条件的一个元素 \(x\) 和一个集合 \(S\) 的方案数。
条件：\(x \notin S\)，\(\gcd\{S\} > 1\)，\(\gcd(x, \gcd\{S\}) = 1\)。
\(n \le 5 \times 10^5\)，元素 \(\leq 10^7\)，答案对 \(10^9+7\) 取模。

思路

考虑求出 \(f_i\) 表示集合中所有数字中与 \(i\) 互质的数字数量。令 \(c_i\) 表示数字 \(i\) 出现的次数。
那么

\[f_i=\sum_{j}c_j\sum_{d|i,d|j}\mu(d) \]

\[=\sum_{d|i}\mu(d)\sum_{d|j}c_j \]

后面那个玩意可以用 Dirichlet 后缀和搞出来，然后再 Dirichlet 前缀和一次就可以求出 \(f\)。
然后考虑求 \(h_i\) 表示选出若干个数，\(\gcd=i\) 的方案数。\(h'_i\) 表示选出若干个数 \(gcd\) 是 \(i\) 的倍数的方案数。那么显然有

\[h'_i=2^{\sum_{d|j}c_j}-1=\sum_{i|j}h_i \]

那么直接把 Dirichlet 前缀和倒序变为差分即可。
最终答案就是

\[\sum^{10^7}_{i=2}f_ih_i \]

时间复杂度 \(O(n\log\log n)\)。

代码

#include <bits/stdc++.h>
using namespace std;

const int N=10000010,MOD=1e9+7;
int n,m,ans,f[N],g[N],h[N],mu[N],prm[N];
bool v[N];

void findprm(int n)
{
	mu[1]=1;
	for (int i=2;i<=n;i++)
	{
		if (!v[i]) prm[++m]=i,mu[i]=-1;
		for (int j=1;j<=m;j++)
		{
			if (i>n/prm[j]) break;
			v[i*prm[j]]=1; mu[i*prm[j]]=-mu[i];
			if (!(i%prm[j])) { mu[i*prm[j]]=0; break; }
		}
	}
}

int fpow(int x,int k)
{
	int ans=1;
	for (;k;k>>=1,x=1LL*x*x%MOD)
		if (k&1) ans=1LL*ans*x%MOD;
	return ans;
}

int main()
{
	scanf("%d",&n);
	for (int i=1,x;i<=n;i++)
	{
		scanf("%d",&x);
		g[x]++; m=max(m,x);
	}
	n=m; m=0;
	findprm(n);
	for (int i=1;i<=m;i++)
		for (int j=n/prm[i];j>=1;j--)
			g[j]=(g[j]+g[j*prm[i]])%MOD;
	for (int i=1;i<=n;i++)
		h[i]=fpow(2,g[i])-1;
	for (int i=1;i<=n;i++)
		f[i]=(g[i]*mu[i]+MOD)%MOD;
	for (int i=1;i<=m;i++)
		for (int j=1;j*prm[i]<=n;j++)
			f[j*prm[i]]=(f[j*prm[i]]+f[j])%MOD;
	for (int i=1;i<=m;i++)
		for (int j=1;j*prm[i]<=n;j++)
			h[j]=(h[j]-h[j*prm[i]]+MOD)%MOD;
	for (int i=2;i<=n;i++)
		ans=(ans+1LL*f[i]*h[i])%MOD;
	printf("%d",ans);
	return 0;
}