分析

• 我们知道，计算乘法很简单，分解质因数比较困难，这也是大部分密码学的原理，例如RSA秘钥。

• 对于这n个数据，我们记录每个数据出现的次数，例如cnt[t]表示t出现的次数。因为$a_i$最大为$10^6$，因此我们可以从1枚举到到$10^6$，对于每个枚举到的数i，记录一下i的倍数有哪些，如果j是i的倍数，则s[j] += cnt[i]，数组s记录的是在这n个数据中每个数据约数的个数（包含自己）。

• 对于输入的数据a[i]，则这n个数中是其约数的数的个数为s[a[i]] - 1。

• 时间复杂度分析：我们会枚举$10^6$次，每次循环次数为$\frac{10^6}{i}$，因此计算量为：

$$ \sum _ {i = 1} ^ {10^6} \frac{10^6}{i} = 10^6 \times (\frac{1}{1} + \frac{1}{2} + … + \frac{1}{10^6}) = 10^6 \times log(10^6) $$

代码

#include <iostream>

using namespace std;

const int N = 1000010;

int a[N];  // 输入的数据
int cnt[N];  // cnt[i]表示i在数组a中出现的次数
int s[N];  // s[a[i]]表示在数组a中,a[i]的约数的个数(包含a[i])

int main() {

    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        cnt[a[i]]++;
    }

    for (int i = 1; i < N; i++)
        for (int j = i; j < N; j += i)
            s[j] += cnt[i];

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

    return 0;
}