1 #include <iostream>  2 #include <cstring>  3 #include <vector>  4 using namespace std;  5   6 typedef __int64 LL;  7 int num;  8 LL n;  9 const int size = 100000; 10 int a[size+10]; 11 bool flag[size+10];     12 bool vis[size+10]; 13 int prime[size+10]; 14 int hash[size+10]; 15 vector<int>ve[size+10]; 16  17 void init( ) 18 { 19     num = 0; 20     memset( vis , true , sizeof(vis) ); 21     vis[0] = vis[1] = false; 22     for( int i = 2 ; i<=size ; i++ ) 23     {     24         if( vis[i] ) 25         { 26             prime[ num++ ] = i; 27             int j = i * 2; 28             while( j<=size ) 29             { 30                 vis[j] = false; 31                 j += i; 32             } 33         } 34     } 35 } 36  37 void fenjie( int y , int x ) 38 { 39     ve[y].clear( ); 40     for( int i = 0 ; i<num&&prime[i]*prime[i]<=x ; i++ ) 41     { 42         if( x%prime[i]==0 ) 43         { 44             ve[y].push_back( prime[i] ); 45             while( x%prime[i]==0 ) 46             { 47                 x /= prime[i]; 48             } 49         } 50     } 51     if( x>1 ) 52     { 53         ve[y].push_back( x );//将x分解出来的话 会有多少个质因子 54     } 55 } 56  57 LL solve( ) 58 { 59     for( int i = 2 ; i<=size ; i++ ) 60     { 61         for( int j = i ; j<=size ; j+=i ) 62         { 63                 if( flag[j] ) 64                     ++ hash[i]; 65         } 66     } 67     LL ans = 0; 68     LL var , sum; 69     int cnt , veSize; 70     for( int i = 0 ; i<n ; i++ ) 71     { 72         veSize = ve[i].size(); 73         sum = 0; 74         for( int j = 1 ; j<( 1<<veSize ) ; j++ ) 75         {         76             cnt = 0; 77             var = 1; 78             for( int k = 0 ; k<veSize ; k++ ) 79             { 80                 if( j&(1<<k) ) 81                 { 82                     ++ cnt; 83                     var *= (LL) ve[i][k]; 84                 } 85             } 86             if( cnt&1 )//奇加偶减 87             { 88                 sum += hash[var]; 89             } 90             else 91             { 92                 sum -= hash[var]; 93             } 94         } 95         if( sum==0 )// sum   与a[i]非 互质的个数  96             continue; 97         ans += (LL)( (sum-1) * ( n-sum ) ); 98     } 99     return ans/2;100 }101 102 int main()103 {104     cin.sync_with_stdio(false);105     init( );106     int t;107     LL ans;108     cin >> t;109     while( t-- )110     {111         memset( hash , 0 , sizeof(hash) );112         memset( flag , false , sizeof(flag) );113         cin >> n;114         for( int i = 0 ; i<n ; i++ )115         {116             cin >> a[i];117             flag[ a[i] ] = true;    118             fenjie( i , a[i] );119         }120         ans = solve( );121         ans = (LL)( n*(n-1)*(n-2)/6 - ans );122         cout << ans << endl; 123     }124     return 0;125 }