正題

題目鏈接:https://www.luogu.com.cn/problem/CF585E

---

題目大意

給出一個大小為$n$的可重集$T$，求有多少個它的非空子集$S$和元素$x$滿足
$x\in /S,gcd\{S\}>1,gcd(S,x)=1$

$1\le n\le 5\times 10^5$，值域范圍是$[2,10^7]$

---

解題思路

$x\in /S$這個條件是沒有用的，可以去掉

然后設$f_i$表示與$i$互質(zhì)的數(shù)的個數(shù)，$s_i$表示$gcd$為$i$的集合個數(shù)，那么答案就是$\sum f_i{s}_i$

然后設$c_i$表示$i$的個數(shù)
$$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; }

總結(jié)

以上是生活随笔為你收集整理的CF585E-Present for Vitalik the Philatelist【莫比乌斯反演,狄利克雷前缀和】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。