题解 | 因子区间

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int find(int x){//计算有多少因子，题解是直接算
    int count=0;
    for(int i=1;i*i<=x;i++){
        if(x%i==0){
            count++;
            if(i!=x/i){
                count++;
            }
        }
    }
    return count;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<vector<int>>a(130);//看了题解知道有130个因子；可以设置更大，也能过
    int x;
    for(int i=1;i<=n;i++){
        cin >> x;
        a[find(x)].push_back(i);//用二维数组统计因子数相同数的位置
    }
    int l, r;
    while (q--) {
        cin >> l >> r;
        ll ans = 0;
        for (int i = 1; i <=128; i++) {
            auto it1 = upper_bound(a[i].begin(), a[i].end(), r);//用迭代器找二维数组每一列有几个数在l,r之间
            auto it2 = lower_bound(a[i].begin(),a[i].end(), l);
            int u = it1 - it2; //迭代器相减等于元素个数
            ans += (ll)u * (u - 1) / 2; //等价于C(u,2)
        }
        cout << ans << endl;
    }
    return 0;
}