基础数学算法-轻拍牛头

题目-轻拍牛头

问题分析

求的是对于当前数字$A_i$, 其他数字有多少个是它的约数
暴力求每个数字是否是当前数字的约数, 算法时间复杂度$O(n^2)$, 无法通过
因为求一个数的约数算法时间复杂度是$O(n\sqrt{n})$, 比较复杂, 但是求一个数的倍数很简单

算法步骤

• 读入每个数字
• 求每个数有多少个数是它的倍数

算法时间复杂度$O(\log n)$

代码实现

#include <bits/stdc++.h>

using namespace std;

// 数据的范围
const int N = 1e6 + 10;

int n, w[N];
int cnt[N];
int ans[N];

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) {
   
        cin >> w[i];
        cnt[w[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[w[i]] - 1 << '\n';
    
    return 0;
}