<span>codeforces 691F Couple Cover（暴力预处理）</span>
题意：
给你一个长度为n的序列，m个询问，每次学问一个数
让你回答序列中乘积不小于它的数对有多少对
思路：
预处理当前序列中不大于当前值的数对有多少，然后用总数减去他的前一个就是答案了
/* *********************************************** Author :devil ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; typedef long long LL; const int inf=0x3f3f3f3f; const int mod=1e9+7; const int N=3e6; int n,m,ma; LL cnt[N],sum[N]; int main() { //freopen("in.txt","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&m); cnt[m]++; ma=max(ma,m); } for(int i=1;i<=ma;i++) for(int j=1;j<=ma;j++) { if(1ll*i*j>N) break; if(i==j) sum[i*j]+=cnt[i]*(cnt[j]-1); else sum[i*j]+=cnt[i]*cnt[j]; } for(int i=2;i<=N;i++) sum[i]+=sum[i-1]; scanf("%d",&m); LL tmp=1ll*n*(n-1); while(m--) { scanf("%d",&ma); printf("%I64d\n",tmp-sum[ma-1]); } return 0; }
投递网易有道等公司10个岗位 >
