题解：SP12304 INVDIV - Smallest Inverse Sum of Divisors

· · 题解

参考资料

题意简述

给定 T 次询问，每次询问一个正整数 n，求最小的正整数 i 使得 \sigma(i)=n。

其中 \sigma(i) 表示 i 的所有正因子的和。

解题思路

思想

显然 \sigma(n)\ge n，因此只需要考虑 i\leq n 的情况即可。

无论采用哪种方法，整体思想都是：

  1. 预处理区间 [1,10^8] 内所有整数 i 的因子和 \sigma(i)。
  2. 在预处理的过程中，为每一个 \sigma(i) 记录其对应的最小整数 i。
  3. 利用预处理结果快速解答所有查询。

朴素算法

分别计算每个数的 \sigma(i)：枚举 \sqrt i 以内的所有因子 d，因为如果 d 是 i 的因子，则 \frac{i}{d} 也是 i 的因子。

时间复杂度为 O(T+n\sqrt n)，不能通过此题。

Dirichlet 前缀和

注意到 \sigma(i) 是 \operatorname{id}(i) 的和函数，因此可以使用 Dirichlet 前缀和 进行计算。

时间复杂度为 O(T+n\log\log n)，实际用时 \sim 6.2\mathrm{s}。

线性筛

初始化 \sigma(1)=1。对于每一个素数 p，有 \sigma(p)=p+1。

对于每一个数 n，当通过 n'\times p_1 的方式筛掉，分类讨论：

  1. 若 n'\bmod p_1=0：

根据约数和函数的性质：

\sigma(n)=\prod_{i=1}^r(1+p_i+p_i^2+\dots+p_i^{a_i-1}+p_i^{a_i})

进一步化简：

\sigma(n)=\frac{\sigma(n')(1+p_1+p_1^2+\dots+p_i^{a_i-1}+p_1^{a_1})}{(1+p_1+p_1^2+\dots+p_1^{a_1-1})}=\frac{\sigma(n')f(n')}{f(n)}

同时维护一个辅助函数 f(n)，表示 n 最小质因子 p_1 的幂次和：

f(n)=1+p_1+p_1^2+\dots+p_1^{a_1-1}+p_1^{a_1}
  1. 否则 n'\bmod p_1\ne 0：

说明 n' 和 p_1 是互质的，根据积性函数性质：

\sigma(n)=\sigma(n')\times\sigma(p_1)

时间复杂度为 O(T+n)，实际用时 \sim 2.7\mathrm{s}。

参考代码

Dirichlet 前缀和

#include <bits/stdc++.h>
using namespace std;

const int N=100000005;
int sigma[N],ans[N];
bool vis[N];
void init()
{
    for(int i=1;i<N;i++)
    {
        sigma[i]=i;
    }
    for(int i=2;i<N;i++)
    {
        if(vis[i])continue;
        for(int j=i;j<N;j+=i)
        {
            vis[j]=1;
            sigma[j]+=sigma[j/i];
        }
    }
    for(int i=1;i<N;i++)
    {
        if(sigma[i]<N&&!ans[sigma[i]])
        {
            ans[sigma[i]]=i;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        cout<<(!ans[n]?-1:ans[n])<<'\n';
    }
    return 0;
}

线性筛

#include <bits/stdc++.h>
using namespace std;

const int N=100000005;
int pri[N],num[N],sigma[N],ans[N];
bool vis[N];
void init()
{
    vis[0]=vis[1]=1;
    num[1]=sigma[1]=1;
    int cnt=0;
    for(int i=2;i<N;i++)
    {
        if(!vis[i])
        {
            pri[++cnt]=i;
            num[i]=sigma[i]=i+1;
        }
        for(int j=1;j<=cnt;j++)
        {
            if(i*pri[j]>=N)break;
            vis[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                num[i*pri[j]]=num[i]*pri[j]+1;
                sigma[i*pri[j]]=sigma[i]/num[i]*num[i*pri[j]];
                break;
            }
            num[i*pri[j]]=pri[j]+1;
            sigma[i*pri[j]]=sigma[i]*sigma[pri[j]];
        }
    }
    for(int i=1;i<N;i++)
    {
        if(sigma[i]<N&&!ans[sigma[i]])
        {
            ans[sigma[i]]=i;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        cout<<(ans[n]?ans[n]:-1)<<'\n';
    }
    return 0;
}