2021牛客暑期多校训练营7

H xay loves count

#include<iostream>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<vector>

#define fi first
#define se second

#define lowbit(x) (x&-x)

using namespace std;

namespace ae86{
    const int bufl=1<<15;
    char buf[bufl],*s=buf,*t=buf;
    inline int fetch(){
        if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
        return*s++;
    }
    inline int read(){
        int a=0,b=1,c=fetch();
        while(!isdigit(c))b^=c=='-',c=fetch();
        while(isdigit(c))a=a*10+c-48,c=fetch();
        return b?a:-a;
    }
}
using ae86::read;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,double> pid;

const int inf=0x3f3f3f3f;
const ll INF=2e18;
const double eps=1e-8;
const int mod=1e9+7;

const int N=1000010;

vector<int> fac[N];
int n;
int cnt[N],a[N];

int main(){        
    n=read();
    int mx=-inf;
    for(int i=1;i<=n;i++){
        a[i]=read();
        cnt[a[i]]++;
        mx=max(mx,a[i]);
    }

    for(int i=1;i<=mx;i++)
        for(int j=1;j<=mx/i;j++){
            fac[i*j].push_back(i);
        }

    ll res=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<fac[a[i]].size();j++){
                res+=1ll*cnt[fac[a[i]][j]]*cnt[a[i]/fac[a[i]][j]];
        }
    }
    printf("%lld",res);
}