题解 P2926 【[USACO08DEC]Patting Heads S】

· · 题解

P2926 题解

做法1：

暴力枚举，但时间复杂度为：

O(n^2)

无法通过本题。

做法2：

从枚举约数的角度思考，对于每个数 a[i] 枚举它所有的约数，然后看这些约数在 n 个数中出现了多少次，对其求和，最后输出；但时间复杂度为：

O(n\sqrt{\smash[b]{A}})

开 O2 也无法通过。

做法3（正解）：

从枚举倍数的角度思考：对于一个数 i 若它在原数组中出现了 c[i] 次，那么 i 这个数会对它的每一个倍数产生 c[i] 的贡献。这样就可以通过查询这样产生的贡献的总和来计算答案了，其时间复杂度为：

O(nlogn)

时间复杂度不高，不用开 O2 即可通过。

代码：

#include <bits/stdc++.h>
using namespace std;
const int Maxn=1000100;//数组大小
const int Bignumber=1000000;
int n,a[Maxn],c[Maxn],w[Maxn];//n个数，数列，数字统计容器，贡献值
int main() {
    scanf("%d",&n);//输入
    for(int i=1;i<=n;i++) {
        scanf("%d",&a[i]);//输入数列
        c[a[i]]++;
    }
    for(int i=1;i<=Bignumber;i++) 
        for(int j=i;j<=Bignumber;j+=i)
            w[j]+=c[i];//i这个数会对j产生c[i]的贡献
    for(int i=1;i<=n;i++) 
        printf("%d\n",w[a[i]]-1);//输出时要把a[i]对自己的贡献减去
    return 0;
}