Untitled

 avatar
user_5379400
plain_text
a month ago
1.9 kB
3
Indexable
Never
#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e6 + 2e4;

int n;
int a[2005];
int f[2001][2001];
int C[maxn];
// a * c = b * d
// a / b = c / d


pair<int, int> get(int a, int b){
  int gcd = __gcd(a, b);
  a /= gcd; b /= gcd;
  return {a, b};
}

bool cmp(pair<pair<int, int>, int> &a, pair<pair<int, int>, int> &b){
  if (a.first.first == b.first.first) return a.first.second < b.first.second;
  return a.first.first < b.first.first;
}

void input(){
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  sort(a + 1, a + 1 + n);
  vector<pair<pair<int, int>, int>> g; 
  for (int i = 1; i <= n; i++){
    for (int j = i + 1; j <= n; j++){
      g.push_back({get(a[i], a[j]), i * (n + 1) + j});
    }
  }
  sort(g.begin(), g.end(), cmp);
  int tlast = -1, mlast = -1, cnt = 0;
  for (auto v : g){
    int i = v.second / (n + 1);
    int j = v.second % (n + 1);
    int t = v.first.first;
    int m = v.first.second;
    if (tlast != t || mlast != m){
      ++cnt;
      tlast = t;
      mlast = m;
    }
    f[i][j] = cnt;
    C[f[i][j]]++;
  }
}

void solve(int testcase){
  input();
  long long ans = 0;  
  for (int i = n; i >= 1; i--){
    for (int j = i - 1; j >= 1; j--){
      C[f[j][i]]--;
    }
    for (int j = i + 1; j <= n; j++){
      ans += C[f[i][j]];
    }
  }
  cout << "#" << testcase << ' ' <<  ans << '\n';
}

int main(){
   // freopen("input.txt", "r", stdin);
  //freopen("output.txt", "w", stdout);
  ios_base::sync_with_stdio(false), cin.tie(0);
  // clock_t start, end;
  // double duration;
  // start = clock();
  int t = 1;
  cin >> t;
  for (int i = 1; i <= t; i++) solve(i);
  // // cout << 1 << endl << 2000 << endl;
  // for (int i = 1; i <= 2000; i++) cout << i << ' ';
  // end = clock();
  // duration = (double)(end - start) / CLOCKS_PER_SEC;
  // printf("interchangeSort take %f seconds", duration);
}
Leave a Comment