题解 | 小红的数组

#include <iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll k;
    cin>>n>>k;
    vector<ll>a(n);
    unordered_map<ll,int>cnt;
    for(int i=0;i<n;i++){
        cin>>a[i];
        cnt[a[i]]++;
    }
    sort(a.begin(),a.end());
    ll less=0;
    int l=0,r=n-1;
    while(l<r){
        if(a[l]>k/a[r])r--;
        else{
            if(a[l]*a[r]<k){
                less+=r-l;
                l++;
            }
            else r--;
        }
    }
    ll equal=0;
    unordered_map<ll,bool>visited;
    for(auto&[num,freq]:cnt){
        if(visited.count(num))continue;
        if(k%num!=0)continue;
        ll t=k/num;
        if(cnt.count(t)){
            if(t==num)equal+=(ll)freq*(freq-1)/2;
            else{
                equal+=(ll)freq*cnt[t];
                visited[t]=true;
            }
        }
        visited[num]=true;
    }
    ll total=(ll)n*(n-1)/2;
    ll more=total-less-equal;
    cout<<more<<" "<<equal<<" "<<less;
    return 0;
}