1161 - Extreme GCD

阅读量：4541 次

发布时间：2019-06-08

本文共 2347 字，大约阅读时间需要 7 分钟。

1161 - Extreme GCD

Time Limit: 1 second(s)

Memory Limit: 32 MB

All of you know that GCD means the greatest common divisor. So, you must have thought that this problem requires finding some sort of GCD. Don't worry, you are absolutely right!

Given N positive integers, not necessarily distinct, how many ways you can take 4 integers from the N numbers such that their GCD is 1.

Input

Input starts with an integer T (≤ 20), denoting the number of test cases.

Each case starts with an integer N (4 ≤ N ≤ 10000). The next line contains N integers separated by spaces. The integers will be positive and not greater than 10000.

Output

For each case, print the case number and the number of ways you can take the integers as mentioned above.

Sample Input

Output for Sample Input

2 4 6 1

1 2 4 6 8

12 46 100 131 5 6 7 8 9 10

Case 1: 1

Case 2: 4

Case 3: 195

SPECIAL THANKS: JANE ALAM JAN (SOLUTION, DATASET)

思路：容斥原理;

和这个一样；

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
             8 #include
             
               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
              
               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
               
                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<
                
                 =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 }

转载于:https://www.cnblogs.com/zzuli2sjy/p/5494847.html

你可能感兴趣的文章