轻拍牛头

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 891 字

每头牛有数字A_i；第i头牛要拍打所有满足“

一本通
练习

正文

/*
原题：T1621「一本通 6.2 练习 2」轻拍牛头（USACO 2008 Dec. Silver）
题意：每头牛有数字 A_i；第 i 头牛要拍打所有满足“A_j 是 A_i 的约数”的牛 j（不含自己）。
思路：统计每个值出现的次数 cnt[v]。对每个出现过的约数 d，把它贡献到其所有倍数 m 上：
total[m]+=cnt[d]。则第 i 头牛的答案 = total[A_i]-1（去掉自己）。
用“枚举约数 d，累加其倍数”的筛法，复杂度 O(M log M)，M=1e6。
复杂度：时间 O(M log M)，空间 O(M)
易错点：1) 答案要减 1（排除自己拍自己）；2) 只遍历出现过的 d 以提速；3) A_i 上限 1e6，数组开够。
*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int MAX=1000000;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin>>N;
    vector<int> a(N+1),cnt(MAX+1,0);
    for(int i=1;i<=N;i++){
        cin>>a[i];
        if(a[i]<=MAX) cnt[a[i]]++;
    }
    vector<int> total(MAX+1,0);
    for(int d=1;d<=MAX;d++){
        if(cnt[d]==0) continue;
        for(int m=d;m<=MAX;m+=d){
            total[m]+=cnt[d];
        }
    }
    for(int i=1;i<=N;i++){
        cout<<total[a[i]]-1<<"\n";
    }
    return 0;
}

轻拍牛头

正文

一本通·提高篇的其它内容