题解：SP1754 DIVSUM2 - Divisor Summation (Hard)

Dark_Blue_Sky · 2025-05-10 13:35:09 · 题解

题解：SP1754 DIVSUM2 - Divisor Summation (Hard)

分析

我先给出一个数的约数和公式：({a_1}^0+{a_1}^1+{a_1}^2+\cdots+{a_1}^{p_1})\times ({a_2}^0+{a_2}^1+{a_2}^2+\cdots+{a_2}^{p_2})\times ({a_3}^0+{a_3}^1+{a_3}^2+\cdots+{a_3}^{p_3})\times \cdots ({a_n}^0+{a_n}^1+{a_n}^2+\cdots+{a_n}^{p_n})。

那么，我们就只需要求出 n 所有的质因数以及每个质因数对应的次数即可计算出最终的答案。

为此，我们可以用筛法预处理出 1 \sim 10^7 中的所有素数，用以代替枚举每个数，以达到优化时间复杂度的效果。

最后，我们只需要枚举 1\sim \sqrt{n} 中的所有素数，算出这些素数的次数，再根据上述公式，即可完成此题。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int vis[100000005];
vector<int> prime;
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    vis[0]=vis[1]=1;
    for(int i=2;i<=100000000;i++){
        if(!vis[i])prime.push_back(i);
        for(int j=1;prime[j-1]*i<=100000000&&j<=prime.size();j++){
            vis[min(i*prime[j-1],100000000ll)]=true;
            if(i%prime[j-1]==0)break;
        }
    }
    int n,x;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        int ans=1,i1=x;
        for(int j=0;prime[j]*prime[j]<=i1&&j<prime.size();j++){
            if(prime[j]==0||prime[j]==1)continue;
            int getting=1,tmp=1;
            while(i1%prime[j]==0){
                getting*=prime[j],tmp+=getting;
                i1/=prime[j];
            }
            ans*=tmp;
        }
        ans*=(1+i1);
        cout<<ans-x<<"\n";
    }
    return 0;
}