思路

首先看到题目，不难想到先将因子数量求出来，求因子数量使用了 线性筛 。

对数字进行唯一分解，

则该数字的因子数量为

随后问题转化为，给一个长度为 的数组，求出区间内使得的数对个数，我们使用 莫队 求解。

代码

#include <bits/stdc++.h>

std::vector<int> prime, minp;
void sieve(int n = 1e7) {
    minp.resize(n + 1);
    for (int i = 2; i <= n; i++) {
        if (!minp[i]) {
            minp[i] = i;
            prime.push_back(i);
        }
        for (auto j : prime) {
            if (j > minp[i] || j > n / i) break;
            minp[i * j] = j;
        }
    }
}

bool isprime(int n) {
    return minp[n] == n;
}

using i64 = long long;

struct MO {
private:
    const std::vector<int>& c;
    int n;
    int block_size;

    struct Query {
        int l, r, block, oid;
    };
    std::vector<Query> ques;

    std::vector<int> freq;
    i64 res;

    std::vector<int> disc;
    int k;

    void add(int idx) {
        int val = disc[idx];
        res += freq[val];
        freq[val]++;
    }

    void sub(int idx) {
        int val = disc[idx];
        freq[val]--;
        res -= freq[val];
    }

public:
    MO(const std::vector<int>& arr) : c(arr), n(arr.size()) {
        block_size = (int)(sqrt(n));
        std::vector<int> has = c;
        std::sort(has.begin(), has.end());
        has.erase(std::unique(has.begin(), has.end()), has.end());
        
        k = has.size();
        disc.resize(n);
        std::unordered_map<int, int> tmp;
        for(int i = 0; i < k; ++i) {
            tmp[has[i]] = i;
        }
        for(int i = 0; i < n; ++i) {
            disc[i] = tmp[c[i]];
        }
    }

    void que(int l, int r) {
        ques.push_back({
            l, r, l / block_size, (int)ques.size()
        });
    }

    std::vector<i64> solve() {
        if (ques.empty()) {
            return {};
        }

        std::sort(ques.begin(), ques.end(), [](const Query& a, const Query& b) {
            if (a.block != b.block) {
                return a.block < b.block;
            }
            return (a.block % 2) ? (a.r < b.r) : (a.r > b.r);
        });

        std::vector<i64> ans(ques.size());
        freq.assign(k, 0);
        res = 0;
        
        int L = 0;
        int R = -1;

        for (const auto& q : ques) {
            int l = q.l, r = q.r;
            
            while (L > l) {
                L--;
                add(L);
            }
            while (R < r) {
                R++;
                add(R);
            }
            while (L < l) {
                sub(L);
                L++;
            }
            while (R > r) {
                sub(R);
                R--;
            }
            
            ans[q.oid] = res;
        }

        return ans;
    }
};

void solve() {
    int n, q;
    std::cin >> n >> q;

    std::vector<int> a(n);
    for (auto& v : a) std::cin >> v;

    std::vector<int> c(n);
    for (int i = 0; i < n; ++i) {
        c[i] = 1;
        int x = a[i];
        std::unordered_map<int, int> cnt;
        while (minp[x]) {
            cnt[minp[x]]++;
            x /= minp[x];
        }

        for (auto [k, v] : cnt) c[i] *= (v + 1);
    }

    // for (int i = 0; i < n; ++i) {
    //     std::cout << c[i] << " \n"[i == n - 1];
    // }

    MO mo(c);

    for (int _ = 0; _ < q; ++_) {
        int l, r;
        std::cin >> l >> r;
        // [l - 1, r - 1]

        mo.que(l - 1, r - 1);
    }

    auto res = mo.solve();
    for (auto v : res) std::cout << v << "\n";
}

int main() {
    std::cin.tie(nullptr) -> sync_with_stdio(false);

    sieve(100'005);

    int t = 1;
    // std::cin >> t;

    while (t--) solve();
}