Untitled
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