洛谷 P2926：轻拍牛头 ← 模拟题

【题目来源】
https://www.luogu.com.cn/problem/P2926
https://www.acwing.com/solution/content/31266/

【题目描述】
今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏。
贝茜让 N 头奶牛（编号 1 到 N）坐成一个圈。
除了 1 号与 N 号奶牛外，i 号奶牛与 i−1 号和 i+1 号奶牛相邻，N 号奶牛与 1 号奶牛相邻。
农夫约翰用很多纸条装满了一个桶，每一张纸条中包含一个 1 到 1000000 之间的数字（可能有重复数字）。
接着每一头奶牛 i 从桶中取出一张纸条，纸条上的数字用 Ai 表示。
所有奶牛都选取完毕后，每头奶牛轮流走上一圈，当走到一头奶牛身旁时，如果自己手中的数字能够被该奶牛手中的数字整除，则拍打该牛的头。
牛们希望你帮助他们确定，每一头奶牛需要拍打的牛的数量。
即共有 N 个整数 A1,A2,…,AN，对于每一个数 Ai，求其他的数中有多少个是它的约数。

【输入格式】
第一行包含整数 N。
接下来 N 行，每行包含一个整数 Ai。

【输出格式】
共 N 行，第 i 行的数字为第 i 头牛需要拍打的牛的数量。

【数据范围】
1≤N≤10^5,
1≤Ai≤10^6

【输入样例】
5
2
1
2
3
4

【输出样例】
2
0
2
1
3

【算法分析】
● 题目描述中，最后一句是核心。其他部分可以视为干扰的内容。
● 特别要注意，最后一句表述中的“其他的数”。这表示，所求结果不包括自己本身。据此，就容易理解代码中的 ans[a[i]]-1 语句了。其中，ans[a[i]] 表示 Ai 的约数的个数。
● 若 A 是 B 的倍数，那么 B 就是 A 的约数。当求约数的时间复杂度过大时，可从它的倍数的角度来考虑解决问题。也就是说，求出某个数的各个倍数的个数，等价于求出这些倍数相对于这个数的约数个数。这样操作，可使本题算法的时间复杂度由暴力算法的 O(n^2) 优化为 O(nlnn)。这是因为，lnn=1+1/2+1/3+……+1/n。
● ​​​​​​​由于会存在相同的数，所以，可先利用桶排序算法统计每个数出现的次数，再利用上文思想进行计算。

【算法代码】

#include<iostream>
using namespace std;

const int maxn=1e5+5;
const int maxm=1e6+5;
int a[maxn];
int cnt[maxm],ans[maxm];
int n;

int main() {
    cin>>n;
    for(int i=0; i<n; i++) {
        cin>>a[i];
        cnt[a[i]]++;
    }

    for(int i=1; i<maxm; i++) {
        if(cnt[i]==0) continue;
        for(int j=i; j<maxm; j+=i) {
            ans[j]+=cnt[i];
        }
    }

    for(int i=0; i<n; i++) {
        cout<<ans[a[i]]-1<<endl;
    }

    return 0;
}

/*
in:
5
2
1
2
3
4

out:
2
0
2
1
3
*/

【参考文献】
https://www.acwing.com/solution/content/31266/
https://www.acwing.com/solution/content/151546/