Codeforces 803F - Coprime Subsequences(数论)

原题链接：http://codeforces.com/contest/803/problem/F

题意：若gcd(a₁, a₂, a₃,...,a_n)=1则认为这n个数是互质的。求集合a中，元素互质的集合的个数。

思路：首先知道一个大小为n的集合有2ⁿ-1个非空子集，运用容斥，对某个数，我们可以求出它作为因子出现的个数（假设为k_i）。推一下式子，可以得到结果就等于：Σmiu[i]*(2ⁱ-1)，其中miu[i]是莫比乌斯函数。

时间复杂度为：O(n*sqrt(max_a))，看起来似乎会超时，实际上用了不到300ms过了。

AC代码：

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<map>

 using namespace std;

 typedef long long LL;

 const LL MOD=1e9+;

 const int MAXN=1e5+;

 int num[MAXN];

 map<int, int> mp;

 int miu[MAXN],primes[MAXN],tot=;

 bool isPrime[MAXN];

 void getMiu()

 {

     memset(isPrime,true,sizeof(isPrime));

     miu[]=;

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

     {

         if(isPrime[i])

         {

             miu[i]=-;

             primes[++tot]=i;

         }

         for(int j=;j<=tot;j++)

         {

             if(i*primes[j]>=MAXN) break;

             isPrime[i*primes[j]]=false;

             if(i%primes[j]==)

             {

                 miu[i*primes[j]]=;

                 break;

             }

             miu[i*primes[j]]=-miu[i];

         }

     }

 }

 LL POW[MAXN];

 void getpow()

 {

     POW[]=;

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

         POW[i]=POW[i-]*%MOD;

     return;

 }

 int main()

 {

     int n,a,maxx;

     getMiu();

     getpow();

     scanf("%d", &n);

     maxx=;

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

         scanf("%d", &a);//cout<<'*'<<endl;

         maxx=max(a, maxx);

         for(int j=;j*j<=a;j++){

             if(a%j==){

                 mp[j]++;

                 if(j*j!=a)

                     mp[a/j]++;

             }

         }

     }

     LL res=;

     for(int i=;i<=maxx;i++){

         if(mp[i]!=){

             res=(res+miu[i]*(POW[mp[i]]-))%MOD;

         }

     }

     res=(res%MOD+MOD)%MOD;

     cout<<res<<endl;

 }

做过多校题HDU6053发现思路差不多，于是一发就AC了特别开心 :D

巴特西

Codeforces 803F - Coprime Subsequences(数论)

最新文章

热门文章