因数计数 参考代码

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn = 100000 + 100;
LL n;
int num[maxn];
LL ans;
LL cnt[maxn], facCnt[maxn], multCnt[maxn];

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> num[i];
        ++cnt[num[i]];
    }
    for (int i = 1; i < maxn; ++i) {
        for (int j = i; j < maxn; j += i) {
            multCnt[i] += cnt[j];
            facCnt[j] += cnt[i];
            if (i == j) {
                --multCnt[i];
                --facCnt[j];
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        ans += multCnt[num[i]];
    }
    ans *= ans;
    for (int i = 0; i < n; ++i) {
        int x = num[i];
        ans -= multCnt[x] * multCnt[x];     // i == j
        ans -= multCnt[x] * facCnt[x] * 2;  // i == l, j == k
        ans -= facCnt[x] * facCnt[x];       // k == l
        ans += multCnt[x];                  // i == j && k == l
        ans += cnt[x] - 1;                  // i == l && j == k
    }
    cout << ans << endl;

    return 0;
}