题解 | 牛客周赛 Round 44 D #因子区间#

D 因子区间

首先，1e5之内的数最多拥有128个因子，所以可以从 1 ~ 128 枚举因子个数，分别计算。

对于每个因子数记录下来该因子数对应的原数组中每个数的下标，二分找到范围内的个数后利用组合数进行计算。时间复杂度

在这之前，可以 预处理1e5内每个数的因子个数.

int n, q;

void solve() {
    cin >> n >> q;
    vector<int> f(maxn, 0); // f[i] 数i的因子数
    for (int i = 1; i <= 100000; i ++) {
        for (int j = i; j <= 100000; j += i) {
            f[j] += 1;
        }
    }
    
    vector<vector<int>> pos(130);
    for (int i = 1; i <= n; i ++) {
        int x;
        cin >> x;
        x = f[x];
        pos[x].push_back(i);
    }
    
    while (q --) {
        int l, r;
        cin >> l >> r;
        ll res = 0;
        for (int i = 1; i <= 128; i ++) {
            auto it1 = upper_bound(all(pos[i]), r);
            auto it2 = lower_bound(all(pos[i]), l);
            int u = it1 - it2;
            res += (ll)u * (u - 1) / 2;
        }
        cout << res << '\n';
    }    
}