题意：\(n \le 5*10^5\) 数列 \(2 \le a_i \le 10^7\)，对于每个数\(a\)满足\(gcd(S)=1,\ gcd(S,a) \neq 1\)的集合称为\(MeowS\)，求\(MeowS\)的个数和
一开始想对于每个数求出有多少个数和它互质，就是没有公因子，容斥一下就是:
所有数-1个公质因子+2个不同公质因子-3... 每个数不同的质因子最多有8个，预处理一下貌似可做 然后看到了的神做法，并没有看明白是什么意思，感觉说错了但是做法是对的然后花了两节课来想为什么，终于想明白了
首先了解一下官方题解的做法：
- 用容斥求\(gcd\neq 1\)的集合数，就是: \[A = (p_i\mid gcd的子集个数)\ -\ (p_ip_j \mid gcd的子集个数)\ +\ (p_ip_jp_k \mid gcd的子集个数)...\]
- 然后对于每个数\(a\)在\(A\)中消去包含它的集合的贡献再计入答案，通过枚举它的不同质因子的组合\(p...\)，在上式中消去这个组合的贡献
看起来好复杂...并且枚举还是\(2^8\)
如何简化这个过程？
我们没有必要求每个数，整体考虑
设质数组合\(p...\)的倍数有\(c\)个，那么它的贡献就是\(2^c-1\)，有多少个数计算的时候没有消去这个贡献呢，\(n-c\)个呀，就是没有这个组合的数！ 计算\(A\)的时候直接乘上这个就行了然后就得到zyf2000的神做法了...
#include#include #include #include #include using namespace std;const int N=5e5+5, M=1e7+5, P=1e9+7;typedef long long ll;inline ll read(){ char c=getchar();ll x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f;}int n, a, m, mi[N];int notp[M], p[M], mu[M], c[M];void sieve(int n) { mu[1] = 1; for(int i=2; i<=n; i++) { if(!notp[i]) p[++p[0]]=i, mu[i]=-1; for(int j=1; j<=p[0] && i*p[j]<=n; j++) { notp[i*p[j]] = 1; if(i%p[j] == 0) {mu[i*p[j]]=0; break;} mu[i*p[j]] = -mu[i]; } }}ll ans=0;int main() { //freopen("in","r",stdin); n=read(); mi[0]=1; for(int i=1; i<=n; i++) a=read(), m=max(m, a), c[a]++, mi[i]=(mi[i-1]<<1)%P; sieve(m); for(int i=1; i<=m; i++) { int tot=0; for(int j=i; j<=m; j+=i) tot += c[j]; (ans += (ll) (n-tot) * (-mu[i]) * (mi[tot]-1) %P )%=P; } cout << (ans+P)%P;}