洛谷题单指南-数学基础问题-P2926 [USACO08DEC] Patting Heads S

原题链接：https://www.luogu.com.cn/problem/P2926

题意解读：有n个数，计算每个数能整除其他数的个数。

解题思路：

a[100005]记录所有的数，h[1000005]记录所有数的个数，cnt[1000005]记录所有数能整除其他数的个数

只需要读入a数组，同时更新h[a[i]]++

再依次从小到大遍历h的下标每一个数i，如果h[i] > 0，则用类似于素数筛的方法，依次判断i的倍数j = 2i，3i，4i....是否存在

如果h[j] > 0，就将cnt[j]++，说明j可以整除的数多了一个

注意相同的数可以有多个，也就是h[i]可能大于1，要记录相同的数也能互相整除，可以把cnt[i]加上h[i] - 1, 

例如：有两个2，h[2] = 2，2能被2整除，cnt[2] += 1 

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, M = 1e6 + 5;

int a[N], h[M], cnt[M]; //a:每头牛的数字  h：每个数字出现的次数 cnt：每个数字能整除的数字个数
int n, maxn;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) 
    {
        scanf("%d", &a[i]);
        h[a[i]]++;
        maxn = max(maxn, a[i]);
    }

    for(int i = 1; i <= maxn; i++)
    {
        if(h[i])
        {
            cnt[i] += h[i] - 1; //h[i]个相同的i，对于i可整除的数增加h[i] - 1
            for(int j = i + i; j <= maxn; j += i)
            {
                if(h[j]) cnt[j] += h[i];
            }
        }
    }

    for(int i = 1; i <= n; i++) printf("%d\n", cnt[a[i]]);
}