CF1822G1 Magic Triples (Easy Ver.) 题解

FFTotoro · 2023-05-06 18:43:08 · 题解

本题可以使用 STL std::map 解决。

记 x 出现的次数为 c_x。考虑先枚举等比三元组中最大的数 x，然后枚举等比三元组的共公比 b，如果 b^2|x，根据乘法原理，答案即为 c_{x/b^2}\cdot c_{x/b}\cdot c_x。另外记得特判三元组中 3 个数相等的情况。时间复杂度 O(n\sqrt{\max\{a_i\}})。

注意到 Easy Version 中 a_i 的值域很小，只有 [1,10^6]；所以 b 的大小是 \sqrt{\max\{a_i\}} 级别的，最大仅有 10^3，该做法可以通过题目。

放代码：

#include<bits/stdc++.h>
#define int long long // 开 long long
using namespace std;
main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,c=0; cin>>n;
    map<int,int> m;
    for(int i=1;i<=n;i++){
      int x; cin>>x; m[x]++; // 统计次数
    }
    for(auto [a,f]:m){
      for(int i=2;i<=1000;i++)
        if(!(a%(i*i)))c+=m[a]*m[a/i]*m[a/(i*i)];
      c+=f*(f-1)*(f-2); // 记得相同的情况
    }
    cout<<c<<endl;
  }
  return 0;
}