fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5.  
  6. vector<int> sieve_primes() {
  7.     const int M = 31623;
  8.     vector<bool> is(M+1, true);
  9.     vector<int> P;
  10.     for (int i = 2; i <= M; i++) {
  11.         if (is[i]) {
  12.             P.push_back(i);
  13.             if ((ll)i * i <= M)
  14.                 for (int j = i*i; j <= M; j += i)
  15.                     is[j] = false;
  16.         }
  17.     }
  18.     return P;
  19. }
  20.  
  21.  
  22. void gen_divisors(ll u, const vector<int>& P, vector<ll>& divs) {
  23.     vector<pair<ll,int>> fac;
  24.     ll x = u;
  25.     for (int p: P) {
  26.         if ((ll)p * p > x) break;
  27.         if (x % p == 0) {
  28.             int e = 0;
  29.             while (x % p == 0) {
  30.                 x /= p;
  31.                 e++;
  32.             }
  33.             fac.emplace_back(p, e);
  34.         }
  35.     }
  36.     if (x > 1) fac.emplace_back(x, 1);
  37.  
  38.  
  39.     function<void(int,ll)> dfs = [&](int i, ll cur) {
  40.         if (i == (int)fac.size()) {
  41.             if (cur <= u) divs.push_back(cur);
  42.             return;
  43.         }
  44.         auto [p, e] = fac[i];
  45.         ll v = 1;
  46.         for (int k = 0; k <= e; k++) {
  47.             dfs(i+1, cur * v);
  48.             v *= p;
  49.         }
  50.     };
  51.     dfs(0, 1);
  52. }
  53.  
  54. int main(){
  55.     ios::sync_with_stdio(false);
  56.     cin.tie(nullptr);
  57.  
  58.     auto primes = sieve_primes();
  59.  
  60.     int T;
  61.     cin >> T;
  62.     while (T--) {
  63.         int n;
  64.         cin >> n;
  65.         vector<ll> a(n);
  66.         for (int i = 0; i < n; i++)
  67.             cin >> a[i];
  68.  
  69.  
  70.         unordered_map<ll,int> freq;
  71.         freq.reserve(n*2);
  72.         for (ll x : a) freq[x]++;
  73.  
  74.         ll ans = 0;
  75.  
  76.         for (auto &kv : freq) {
  77.             ll u = kv.first;
  78.             ll fu = kv.second;
  79.  
  80.  
  81.             vector<ll> divs;
  82.             gen_divisors(u, primes, divs);
  83.  
  84.  
  85.             for (ll x : divs) {
  86.                 ll y = u * (u / x);
  87.                 auto it = freq.find(y);
  88.                 if (it == freq.end()) continue;
  89.                 ll fx = freq[x], fy = it->second;
  90.  
  91.                 if (x < y) {
  92.                     ans += fu * fx * fy;
  93.                 }
  94.                 else if (x == y) {
  95.  
  96.                     if (fu >= 3) {
  97.                         ans += fu * ( (fu-1LL)*(fu-2LL)/2 );
  98.                     }
  99.                 }
  100.             }
  101.         }
  102.  
  103.         cout << ans << "\n";
  104.     }
  105.     return 0;
  106. }
  107.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
7
5
1 7 7 2 7
3
6 2 18
9
1 2 3 4 5 6 7 8 9
4
1000 993 986 179
7
1 10 100 1000 10000 100000 1000000
8
1 1 2 2 4 4 8 8
9
1 1 1 2 2 2 4 4 4
stdout
copy 
3
1
3
0
9
16
36
https://ideone.com/z4x9Un
language:
C++14 (gcc 8.3)
created:
8 days 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!