题解 | 因子区间

#include <iostream>
using namespace std;
#include<vector>
#include<map>
#include<cmath>
int main() {

    int n,q;
    cin>>n>>q;
    vector<map<int,int>> v(n+1);
    vector<long long> arr(n+1);
    vector<long long> allct(n+1);
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        v[i]=v[i-1];
        int ct=0;
        for(int j=1;j<=sqrt(x);j++)
        {
            if(x%j==0)
            {    ct++;
            if(x/j>j)
            ct++;
            }
        }
        //cout<<ct<<endl;
        arr[i]=arr[i-1];
        int cc=v[i][ct];
        if(cc>=1)
        arr[i]=arr[i]+v[i][ct];
        v[i][ct]++;
        allct[i]=ct;
        //cout<<arr[i]<<endl;
        
    }

    while(q--)
    {
        int a,b;
        cin>>a>>b;
        long long result=arr[b]-arr[a-1];
        for(auto i:v[a-1])
        {
            long long ansb=v[b][i.first];
            result-=i.second*(ansb-i.second);
        }
        cout<<result<<endl;
    }

}
// 64 位输出请用 printf("%lld")