CF585E：Present for Vitalik the Philatelist

n<=500000个2<=Ai<=1e7的数，求这样选数的方案数：先从其中挑出一个gcd不为1的集合，然后再选一个不属于该集合，且与该集合内任意一个数互质的数。

好的统计题。

其实就是要对每个数求和他互质的，gcd不为1的集合数，容斥一下，求出所有gcd不为1的集合数A然后减去所有他的质因子对这个A的贡献。（这里的A是CF的题解的B）

那先看看所有gcd不为1的集合数怎么求。比如说2的倍数有cnt_2个，那能凑出2^cnt_2-1个集合，然后3的倍数有cnt_3个，能凑出2^cnt_3-1个集合，但有一些gcd为6的集合被算了两次，就要减去2^cnt_6-1，等等这不是莫比乌斯函数嘛，所以现在只要统计1~1e7中每个数作为多少个数的因数即可。那要把n个数都进行分解，这里可以在筛莫比乌斯的时候记一下每个数的最小质因子就可以n*logMax的时间内完成所有数的分解。由于miu_i=0的cnt_i对答案没贡献，所以每个数分解完的质因子不用去考虑那些次数大于1的部分，比如12=2*2*3直接看2和3即可。把不重复质数分解出来后，在1e7内一个数最多有8个不同质因子，所以枚举一下所有这些质因子能凑出的数即可计算miu_i不为0的cnt_i。

然后某个数的质因子对A的贡献呢？同理耶！

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 #include<stdlib.h>

 //#include<iostream>

 using namespace std;

 int n;

 #define maxn 500011

 #define maxm 10000011

 const int mod=1e9+;

 int a[maxn];

 int xiao[maxm],miu[maxm],prime[maxm],lp;bool notprime[maxm];

 void pre(int n)

 {

     lp=;notprime[]=;

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

     {

         if (!notprime[i]) {prime[++lp]=i;miu[i]=-;}

         for (int j=;j<=lp && 1ll*prime[j]*i<=n;j++)

         {

             notprime[prime[j]*i]=;

             xiao[prime[j]*i]=prime[j];

             if (!(i%prime[j])) {miu[i*prime[j]]=;break;}

             else miu[i*prime[j]]=-miu[i];

         }

     }

 }

 int cnt[maxm],two[maxn];

 int frac[],lf;

 int main()

 {

     scanf("%d",&n);int Max=;

     for (int i=;i<=n;i++) scanf("%d",&a[i]),Max=max(Max,a[i]);

     two[]=;for (int i=;i<=n;i++) two[i]=(two[i-]<<)%mod;

     pre(Max);

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

     {

         int tmp=a[i];lf=;

         while (xiao[tmp])

         {

             int now=xiao[tmp];

             while (xiao[tmp]==now) tmp/=xiao[tmp];

             frac[++lf]=now;

         }

         if (!lf || frac[lf]!=tmp) frac[++lf]=tmp;

         for (int i=;i<(<<lf);i++)

         {

             int now=;

             for (int j=;j<=lf;j++) if (i&(<<(j-))) now*=frac[j];

             cnt[now]++;

         }

     }

     int A=;

     for (int i=;i<=Max;i++) A=(A-miu[i]*(two[cnt[i]]-))%mod;

     int ans=;

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

     {

         int tmp=a[i];lf=;

         while (xiao[tmp])

         {

             int now=xiao[tmp];

             while (xiao[tmp]==now) tmp/=xiao[tmp];

             frac[++lf]=now;

         }

         if (!lf || frac[lf]!=tmp) frac[++lf]=tmp;

         int B=;

         for (int i=;i<(<<lf);i++)

         {

             int now=;

             for (int j=;j<=lf;j++) if (i&(<<(j-))) now*=frac[j];

             B=(B-miu[now]*(two[cnt[now]]-))%mod;

         }

         ans=((ans+A)%mod-B)%mod;

     }

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

     return ;

 }

巴特西

CF585E：Present for Vitalik the Philatelist

最新文章

热门文章