分析:开一个300w的数组,统计,然后nlogn统计每个值在在序对第一个出现有多少种情况
时间复杂度:O(nlogn) n在3e6数量级
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N = 3e6;
const LL mod = 1e9+;
LL n,m,sum[N+],c[N+];
int main(){
scanf("%I64d",&n);
int mx=;
for(int i=;i<=n;++i){
int x;scanf("%d",&x);++c[x];
mx=max(x,mx);
}
for(int i=;i<=mx;++i){
for(int j=;j<=mx;++j){
if(1ll*i*j>N)break;
if(i==j)sum[i*j]+=c[i]*(c[i]-);
else sum[i*j]+=c[i]*c[j];
}
}
for(int i=;i<=N;++i)sum[i]+=sum[i-];
scanf("%I64d",&m);
while(m--){
int p;
scanf("%d",&p);
printf("%I64d\n",n*(n-)-sum[p-]);
}
return ;
}