U523244 题解

zhujianheng · 2025-09-23 20:50:12 · 个人记录

注意到 A_i,A_j 必须是 A_k 的因数，考虑先 O(V \log V) 存下所有可能的因数，用 vector 存下之后再考虑枚举 k，然后枚举 A_k 的所有因数 x，平均为 O(\log V) 个，然后再用 map 记录所有出现的数的位置，由于只有 10^6，可以不用 map，用桶（但标程中用的 map，后来才知道可以爆标），然后每回求出 x 和 \dfrac{A_k}{x} 是否存在于数组 A 中，如果存在，因为数组数互不相等，所以只要满足题目中的 1 \le i < j < k \le n，就直接加 1，标程此部分时间复杂度 O(n \log n \log V) 的，但可以只用 O(n \log V) 完成。

时间复杂度 O((V+n \log n)\log V)，空间 O(n+V \log V)，如果用桶的话时间 O((V+n) \log V)，空间 O(n+V+V \log V)。

当然本题还有个 O(n \log n \sqrt V) 的做法和一个 O(n^3) 的暴力法，但不优，被我后来想到的 O(V \log V+n \log n \log V) 给创飞了，然后又被 O((n+V) \log V) 给创飞了。

所以这题其实完全可以给 10^6，卡双 \log。

懂了，下次出个加强版，同样的题解。

标程：

#include<bits/stdc++.h>
using namespace std;
const int N=200009,V=1000009;
int a[N];
vector<int> G[V];
map<int,int> mp;
void init(int n){
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j+=i)
            G[j].push_back(i);
}
int main(){
    ios::sync_with_stdio(0); 
    int n,v=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        v=max(v,a[i]);
        mp[a[i]]=i;
    }
    init(v);
    long long ans=0;
    for(int k=1;k<=n;k++)
        for(int p=0;p<G[a[k]].size();p++){
            int x=G[a[k]][p];
            if(!mp[x]) continue;
            if(!mp[a[k]/x]) continue;
            if(mp[x]>mp[a[k]/x]||mp[a[k]/x]>k||mp[x]>k) continue;
            ans++;
        }
    cout<<ans<<endl;
    return 0;
}