AT_abc249_d [ABC249D] Index Trio 题解

· · 题解

前言。

今天正好在家休息，于是写一篇题解庆祝一下。

这个题是一个简单的暴力题。

分析。

由题目得 \frac{a_i}{a_j}=a_k 然后进行变换，等式两边同时乘 a_j 得 a_k \times a_j=a_i 的式子。因为 N 的范围比较小，且值域比较小，所以考虑暴力枚举。

那么最朴素的做法就是直接暴力 3 层循环，很显然，我们将收获一个超时大礼包。

那么如何优化呢？考虑桶。我们用桶去存 a_i,a_j,a_k 这三个数是否存在，然后先遍历选定的数 a_j 作为第一层循环，再遍历可以与它相搭配的数 a_k 作为第二层循环，最后去找是否有一个数 a_i 正好等于 a_k\times a_j 的值。

如果您没有看懂这个步骤，那请您再看一眼最初提出的式子。

最后加上可能性，注意到数字有可能重复，所以相同数字的三元组但组合方式不同时，有每个数乘积个可能结果，所以答案可能很大。

代码如下，仅供参考：

#include<iostream>
#include<vector>
using namespace std;
int n,a[200005];
vector<int> t(200005);
//用变长数组去存这些数。
long long ans;
int main(){
    cin>>n;
    for (int i=0;i<n;i++){
        cin>>a[i];
        t[a[i]]++;
    }
    //开始暴力枚举。
    for (int i=1;i<=200000;i++){
        for (int j=1;i*j<=200000;j++){
            ans+=(long long)t[i]*t[j]*t[i*j];
        }
    }
    //注意类型转换。
    cout<<ans<<"\n";
    return 0;
}

后记。

大家如有疑问，可以在评论区提出，我会尽力解答的。