hdu 5072 Coprime

http://acm.hdu.edu.cn/showproblem.php?pid=5072

题意：给出 n 个互不相同的数，求满足以下条件的三元无序组的个数：要么两两互质要么两两不互质。

思路：根据同色三角形原理求，白书105页。求它不符合条件的情况数，先对每一个数分解质因子，然后利用容斥求出与这个数不互质的数的个数，那么不符合条件的的情况数加上（x-1）*(n-x); x为其它数与这个数不互质的个数。最后总的情况数减去不符合的情况数，剩下的就是答案。再求多少个是这个数的倍数的时候，可以用筛法求出。

 #include <cstdio>

 #include <cstring>

 #include <vector>

 #include <algorithm>

 #define maxn 100010

 using namespace std;

 int t,n;

 int a[maxn+];

 int num[maxn+];

 int cnt[maxn+];

 vector<int>g;

 int main()

 {

     scanf("%d",&t);

     while(t--)

     {

         memset(cnt,,sizeof(cnt));

         memset(num,,sizeof(num));

         scanf("%d",&n);

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

         {

             scanf("%d",&a[i]);

             num[a[i]]++;

         }

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

         {

             for(int j=i; j<=maxn; j+=i)

             {

                 cnt[i]+=num[j];

             }

         }

         __int64 ans=;

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

         {

             if(num[i])

             {

                 int m=i;

                 g.clear();

                 for(int j=; j*j<=i; j++)

                 {

                     if(m%j==)

                     {

                         g.push_back(j);

                         while(m%j==) m/=j;

                     }

                 }

                 if(m>) g.push_back(m);

                 int x=(int) g.size();

                 int cc=;

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

                 {

                     int t2=;

                     int xx=;

                     for(int k=; k<x; k++)

                     {

                         if((<<k)&j)

                         {

                             t2++;

                             xx*=g[k];

                         }

                     }

                     if(t2%) cc+=cnt[xx];

                     else  cc-=cnt[xx];

                 }

                 ans+=(__int64)max(cc-,)*(n-cc);

             }

         }

         __int64 t1=(__int64)n*(n-)*(n-)/;

         printf("%I64d\n",t1-ans/);

     }

     return ;

 }

巴特西

hdu 5072 Coprime

最新文章

热门文章