正题

题目链接:https://www.luogu.com.cn/problem/CF585E

题目大意

给出一个大小为\(n\)的可重集\(T\)，求有多少个它的非空子集\(S\)和元素\(x\)满足

\(x\notin S,gcd\{S\}>1,gcd(S,x)=1\)

\(1\leq n\leq 5\times 10^5\)，值域范围是\([2,10^7]\)

解题思路

\(x\notin S\)这个条件是没有用的，可以去掉

然后设\(f_i\)表示与\(i\)互质的数的个数，\(s_i\)表示\(gcd\)为\(i\)的集合个数，那么答案就是\(\sum f_is_i\)

然后设\(c_i\)表示\(i\)的个数

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

然后可以处理出一个\(g_d=\sum_{d|j}c_j\)就可以了。

然后考虑\(s_i\)怎么处理

\[s_i=2^{c_i}-1-\sum_{i|d}(2^{c_d}-1)
\]

就好了。

然后这些都可以用狄利克雷前缀/后缀和\(O(n\log \log n)\)求

code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1e7+1,P=1e9+7;

int n,cnt,pri[N],mu[N],f[N],s[N],pw[N],ans;

bool v[N];

int main()

{

	mu[1]=1;

	for(int i=2;i<N;i++){

		if(!v[i])pri[++cnt]=i,mu[i]=-1;

		for(int j=1;j<=cnt&&i*pri[j]<N;j++){

			v[i*pri[j]]=1;

			if(i%pri[j]==0)break;

			mu[i*pri[j]]=-mu[i];

		}

	}

	scanf("%d",&n);

	for(int i=1;i<=n;i++){

		int x;scanf("%d",&x);

		f[x]++;;

	}

	pw[0]=1;

	for(int i=1;i<N;i++)pw[i]=pw[i-1]*2ll%P;

	for(int j=1;j<=cnt;j++)

		for(int i=N/pri[j];i>=1;i--)

			f[i]+=f[i*pri[j]];

	for(int i=1;i<N;i++)s[i]=pw[f[i]]-1;

	for(int i=1;i<N;i++)f[i]=f[i]*mu[i];

	for(int j=cnt;j>=1;j--)

		for(int i=1;i*pri[j]<N;i++)

			f[i*pri[j]]+=f[i];

	for(int j=cnt;j>=1;j--)

		for(int i=1;i*pri[j]<N;i++)

			(s[i]-=s[i*pri[j]])%=P;

	for(int i=2;i<N;i++)

		(ans+=1ll*f[i]*s[i]%P)%=P;

	printf("%d\n",(ans+P)%P);

	return 0;

}

巴特西

CF585E-Present for Vitalik the Philatelist【莫比乌斯反演,狄利克雷前缀和】

正题

题目大意

解题思路

code

最新文章

热门文章