Untitled

user_5379400
plain_text
a month ago
1.5 kB
9
Indexable
Never
```#include<iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int maxn = 2e6 + 2e4;

int n;
int a[2005];
int f[2001][2001];
int C[maxn];

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++){
int gcd = __gcd(a[i], a[j]);
g.push_back({{a[i] / gcd, a[j] / gcd}, 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(){
ios_base::sync_with_stdio(false), cin.tie(0);
int t = 1;
cin >> t;
for (int i = 1; i <= t; i++) solve(i);
}```