拍打牛头 Patting Heads S

筛约数 T3 https://www.luogu.com.cn/problem/P2926

题面

今天是贝茜的生日，为了庆祝自己的生日，贝茜邀你来玩一个游戏。

贝茜让 $N$ ($1\le N\le 10^5$) 头奶牛坐成一个圈。除了 $1$ 号与 $N$ 号奶牛外，$i$ 号奶牛与 $i-1$ 号和 $i+1$ 号奶牛相邻。$N$ 号奶牛与 $1$ 号奶牛相邻。农夫约翰用很多纸条装满了一个桶，每一张包含了一个不一定是独一无二的 $1$ 到 $10^6$ 的数字。

接着每一头奶牛 $i$ 从柄中取出一张纸条 $A_i$。每头奶牛轮流走上一圈，同时拍打所有手上数字能整除在自己纸条上的数字的牛的头，然后做回到原来的位置。牛们希望你帮助他们确定，每一头奶牛需要拍打的牛。

输入格式

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains a single integer: $A_i$

输出格式

* Lines 1..N: On line i, print a single integer that is the number of other cows patted by cow i.

样例 #1

样例输入 #1

5 
2 
1 
2 
3 
4

样例输出 #1

2 
0 
2 
1 
3

提示

The 5 cows are given the numbers 2, 1, 2, 3, and 4, respectively.

The first cow pats the second and third cows; the second cows pats no cows; etc.

思路

大意是给 n 个数 $A_i$, 对于第 $i$ 个数 $A_i$ 求出序列中其他能整除 $A_i$ 的数的个数。

暴力求一个数的约数是 $O(N\sqrt{N})$ 大概率会超时， 需要找个方法优化。

从约数出发逆向通过求其倍数来筛掉大数。

先把输入的数组统计每个数出现的次数 $cnt[i]$, 然后遍历区间 $i=[1,1e6]$, 接着枚举 $i$ 的倍数 $j$。此时 $i$ 就是 $j$ 的约数， 让 $ans[j]+=cnt[i]$ 即可。

代码

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e6 + 10;
int a[N];
int cnt[N], ans[N];
 
void solve() {
    int n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        cnt[a[i]]++;
    }
    for(int i = 1; i < N; i++)
    {
        for(int j = i; j < N; j += i)
            ans[j] += cnt[i];
    }
 
    for(int i = 0; i < n; i++)
        cout << ans[a[i]] - 1 << endl;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
    return 0;
}