2025.11.1日每日一题

标签：前缀和/二分法

语法： 注意开 long long 的答案，乘法要记得乘以 1LL

题目里提到因子，我们要把输入的 a 数列处理成相对应的因子： 大致有两种算法

第一种是暴力遍历

    for(int j=1;j<N;j++){
    for(int i=1;i*i<=j;i++){
        if(j%i==0) now[j]+=2;
        if(i*i==j) now[j]--;
    }
    }

如果整除的话数字就加上2，最后再判断是不是重复计算了。

第二种是类似于筛法

    for(int i=1;i<=100000;i++){
        for(int j=i;j<=100000;j+=i)
            now[j]++;
    }

把每个因子相对的倍数都加上1，一劳永逸，把全部都算出来了。

后面考虑答案

答案是在某个区间内部的数对个数，比如因子是2的有 个，那么用 来表示。 把所有因子的组数加起来就是答案。

-- btw 1e5内的因子数最多为 128

大致有两种算法

第一种：用前缀和

对于一个因子数 ，把所有的因子数为 的位置标为1，那么 里面的因子的个数就是区间内数的和，然后遍历一下因子从1到130就行。

    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        sum[i][now[x]]=1;
    }
    for(int i=1;i<=130;i++){
        for(int j=1;j<=n;j++){
            sum[j][i]=sum[j-1][i]+sum[j][i];
        }
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        long long ans=0;
        for(int i=1;i<=130;i++)
            ans+=1LL*(sum[r][i]-sum[l-1][i])*(sum[r][i]-sum[l-1][i]-1)/2;
        cout<<ans<<endl;
    } 

第二种：是用二分法

把每个因子 相对应的位置push到一个vector里面，然后用二分法看看有几个。

    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        pos[now[x]].push_back(i);
    }
    while(q--){
        long long ans=0;
        int l,r;
        cin>>l>>r;
        for(int i=1;i<=130;i++){
            auto it1=lower_bound(pos[i].begin(), pos[i].end(), l);
            auto it2=upper_bound(pos[i].begin(), pos[i].end(), r);
            ans+=1LL*(it2-it1)*(it2-it1-1)/2;
        }
        cout<<ans<<endl;
        
    }

复杂度分析

前缀和 处理， 查询， 二分法 查找