1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<string.h>
  5 #include<queue>
  6 #include<stack>
  7 #include<map>
  8 #include<math.h>
  9 using namespace std;
 10 typedef long long LL;
 11 bool prime[10005]= {0};
 12 int ans[10005];
 13 int aa[10005];
 14 int bt[10005];
 15 int cc[10005]= {0};
 16 bool dd[10005]= {0};
 17 queue<int>que;
 18 int main(void)
 19 {
 20         int i,j,k;
 21         for(i=2; i<200; i++)
 22         {
 23                 for(j=i; i*j<=10000; j++)
 24                 {
 25                         prime[i*j]=true;
 26                 }
 27         }
 28         int cnt=0;
 29         for(i=2; i<=10000; i++)
 30         {
 31                 if(!prime[i])
 32                 {
 33                         ans[cnt++]=i;
 34                 }
 35         }int d;
 36         cin>>d;int s;
 37         for(s=1;s<=d;s++)
 38         {       cin>>k;
 39                 memset(bt,0,sizeof(bt));
 40                 for(i=0; i<k; i++)
 41                 {
 42                         scanf("%d",&aa[i]);
 43                 }
 44                 for(i=0; i<k; i++)
 45                 {
 46                         int nn=aa[i];
 47                         int t=0;
 48                         int flag=0;
 49                         while(nn>1)
 50                         {
 51                                 if(flag==0&&nn%ans[t]==0)
 52                                 {
 53                                         flag=1;
 54                                         que.push(ans[t]);
 55                                         nn/=ans[t];
 56                                 }
 57                                 else if(nn%ans[t]==0)
 58                                 {
 59                                         nn/=ans[t];
 60                                         flag=1;
 61                                 }
 62                                 else
 63                                 {
 64                                         flag=0;
 65                                         t++;
 66                                 }
 67                         }
 68                         if(nn>1)
 69                         {
 70                                 que.push(nn);
 71                         }
 72                         int xx=0;
 73                         while(!que.empty())
 74                         {
 75                                 cc[xx++]=que.front();
 76                                 que.pop();
 77                         }
 78                         int x;
 79                         int y;
 80                         for(x=1; x<=(1<<xx)-1; x++)
 81                         {
 82                                 int ak=1;
 83                                 int vv=0;
 84                                 for(j=0; j<xx; j++)
 85                                 {
 86                                         if(x&(1<<j))
 87                                         {
 88                                                 vv++;
 89                                                 ak*=cc[j];
 90                                         }
 91                                 }
 92                                 bt[ak]+=1;
 93                                 if(vv%2)
 94                                         dd[ak]=true;
 95                         }
 96                 }
 97                 LL sum=0;
 98                 LL sum1=0;
 99                 for(i=2; i<=10000; i++)
100                 {
101                         if(bt[i]>=4)
102                         {
103                                 LL nn=(LL)bt[i]*(LL)(bt[i]-1)*(LL)(bt[i]-2)*(LL)(bt[i]-3)/24;
104                                 if(dd[i])
105                                         sum+=nn;
106                                 else sum-=nn;
107                         }
108                 }
109                 sum1=(LL)k*(LL)(k-1)*(LL)(k-2)*(LL)(k-3)/24;
110                 sum1-=sum;printf("Case %d: ",s);
111                 printf("%lld\n",sum1);
112         }
113         return 0;
114 }

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。