fork(2) download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int N = 100009;
  6.  
  7. int t, n, masti[N], ap[1 << 17];
  8. vector<int>v;
  9.  
  10. bool good (int x)
  11. {
  12.    for(int i = 2; i * i <= x; i ++)
  13.       if(x % i == 0) return 0;
  14.    return x != 1;
  15. }
  16.  
  17. void getPr ()
  18. {
  19.    for(int i = 2; i <= 47; i++)
  20.       if(good(i))
  21.         v.push_back(i);
  22. }
  23.  
  24. template < class T>
  25. T readInt () {
  26. 	bool minus = false;
  27. 	T result = 0;
  28. 	char ch;
  29. 	ch = getchar();
  30. 	while (true) {
  31. 		if (ch == '-') break;
  32. 		if (ch >= '0' && ch <= '9') break;
  33. 		ch = getchar();
  34. 	}
  35. 	if (ch == '-') minus = true; else result = ch-'0';
  36. 	while (true) {
  37. 		ch = getchar();
  38. 		if (ch < '0' || ch > '9') break;
  39. 		result = result*10 + (ch - '0');
  40. 	}
  41. 	if (minus)
  42. 		return -result;
  43. 	else
  44. 		return result;
  45. }
  46.  
  47. void solve ()
  48. {
  49.    memset(ap, 0, sizeof(ap));
  50.   scanf("%d", &n);
  51.    for(int i = 1 ; i <= n ; i++)
  52.    {
  53.       int mask = 0;long long x;
  54.      scanf("%lld", &x);
  55.       for(int j = 0; j < 15; j++)
  56.          if(x % v[j] == 0)
  57.            mask |= 1 << j;
  58.       ++ap[mask];
  59.    }
  60.  
  61.    long long ans = 0, cans;
  62.    int nr = (1 << 15) - 1, sz = 0;
  63.  
  64.    for(int i = 0; i < (1 << 16); i++)
  65.       for(int j=1;j<=ap[i];j++)masti[sz++]=i;
  66.  
  67.    for(int s=0;s<sz;s++)
  68.    {
  69.       int val = masti[s];
  70.       int opus = (~val) & nr;
  71.       cans = 0;
  72.       for(int cur = opus; ; cur = (cur - 1) & opus)
  73.       {
  74.          cans += ap[cur];
  75.          for(int j = val; j ; j -= j & -j)
  76.            cans += ap[cur | (j & -j)];
  77.          if(cur == 0) break;
  78.       }
  79.  
  80.       int nrn = 1;
  81.       while(s + 1 < sz && masti[s+1] == masti[s]) s++, nrn++;
  82.       ans += cans * nrn;
  83.    }
  84.  
  85.    printf("%lld\n", ans);
  86. }
  87.  
  88. int main()
  89. {
  90.    #ifndef ONLINE_JUDGE
  91.    freopen("data.in","r",stdin);
  92.    #endif
  93.    getPr ();srand(time(0));
  94.    scanf("%d", &t);
  95.    while(t--)
  96.    solve();
  97.       return 0;
  98. }
  99.  
Success #stdin #stdout 0s 4356KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/Ed7eCW
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!