[ An Ac a Day ^_^ ] CodeForces 691F Couple Cover 花式暴力

时间：2023-03-08 22:30:47
[ An Ac a Day ^_^ ] CodeForces 691F Couple Cover 花式暴力
Time Limit: 3000MS   Memory Limit: 524288KB   64bit IO Format: %I64d & %I64u

Description

方宝宝有n个篮球，每个篮球上写有一个值ai。他第一次从n个篮球中取出1个，不放回。第二次再在剩余的篮球中取出一个。
（每个球被取概率相同）。如果这两个球上的值的乘积大于等于p，他会变得高兴，然后请大家吃饭。否则方宝宝会不高兴，
然后暴食暴饮变得更胖。
当然为了方宝宝的健康（被请吃饭），我想取一个合适的p值，使方宝宝高兴。
那么问题来了，现在有m个数:p1，p2……pm.对于每个p值有多少种选法使方宝宝高兴。
于是善（毒）良（瘤）的出题人把这个问题交给了你们。

Input

第一个行的数是n，第二行是个篮球上面的值ai，第三行是m，第四行p1, p2, p3……pm.
1<=n<=10^6,1<=m<=10^6,1<=pi<=3*10^6,1<=ai<=10^6

Output

第i行输出对于当前pi值，方宝宝能赢的方案数。

Sample Input

输入:
5
4 2 6 1 3
4
1 3 5 8
输出：
20
18
14
10
输入：
2
5 6
2
30 31
输出：
2

Source

好不容易看到一道CF的中文题（原题是英文的） 果断就做了……
题意：
有n个篮球 不放回取出两个球a b
对于m组提问 问对每个pi a*b>=pi的取法有多少种
思路：
根据样例可以分析出来(a=5,b=6)和(a=6,b=5)是两种方法
所以算出来的正常值应该乘2
而且时间限制3000ms 内存限制也很大 就想到暴力了
开两个3e6的数组 计算之前先预处理一下
最后输出n*(n-1)-sum[n-1]  这个式子就已经是乘2的了
 #include<stdio.h>

 #include<iostream>

 #include<algorithm>

 #include<math.h>

 #include<string.h>

 #include<string>

 #include<map>

 #include<set>

 #include<vector>

 #include<queue>

 #define M(a,b) memset(a,b,sizeof(a))

 using namespace std;

 typedef long long ll;

 const int maxn=3e6+;

 ll cnt[maxn];

 ll sum[maxn];

 ll n,m,a,max_=-;

 int main(){

     scanf("%I64d",&n);

     for(int i=;i<n;i++){

         scanf("%d",&m);

         cnt[m]++;

         if(m>max_) max_=m;

     }

     for(int i=;i<=max_;i++){

         for(int j=;j<=max_;j++){

             if(i*j>maxn) break;

             sum[i*j]+=cnt[i]*cnt[j];

             if(i==j) sum[i*j]-=cnt[j];

         }

     }

     for(int i=;i<=maxn;i++)

         sum[i]+=sum[i-];

     scanf("%I64d",&m);

     for(int i=;i<m;i++){

         scanf("%d",&a);

         printf("%I64d\n",n*(n-)-sum[a-]);

     }

     return ;

 }

 /*

 5

 4 2 6 1 3

 4

 1 3 5 8

 2

 5 6

 2

 */