题解 | 因子区间

注意到因子个数比较少，所以直接暴力的来使用前缀和来查询区间里面有多少个相同的因子，然后组合数学一下，得到共有多少匹配就行了。

#include <bits/stdc++.h>
#define il inline

using namespace std;
using ll = long long;
using ull = unsigned long long;
using int128=__int128_t;

const ll N = 2e5 + 5, mod =1e9+7, inf = 2e18;
const double esp=1e-9;
double PI=3.1415926;

il void solve(){
    int n,q;
    cin>>n>>q;
    vector<ll>a(n+1);
    vector<vector<ll>>per(n+5,vector<ll>(130));
    for(int i=1;i<=n;i++){
        cin>>a[i];
        int cnt=0;
        for(ll p=1;p*p<=a[i];p++){
            if(a[i]%p==0){
                cnt++;
                if(p*p!=a[i])cnt++;
            }
        }
        per[i][cnt]++;
        for(int j=1;j<=128;j++){
            per[i][j]+=per[i-1][j];
        }
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        ll ans=0;
        for(int i=1;i<=128;i++){
            ll cnt=per[r][i]-per[l-1][i];
            //1+2+……cnt-1
            ans+=cnt*(cnt-1)/2;
        }
        cout<<ans<<'\n';
    }
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int t = 1;

    //cin >> t;

    while (t--) {

        solve();

    }

    return 0;
}