题解：SP12304 INVDIV - Smallest Inverse Sum of Divisors

原题链接

• 洛谷 SP12304 INVDIV - Smallest Inverse Sum of Divisors

参考资料

• 狄利克雷生成函数 - OI Wiki
• 筛法 - OI Wiki

题意简述

给定 $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})$，实际用时 $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+\cdots+p_i^{a_i-1}+p_i^{a_i})$$

进一步化简：

$$\sigma{(n)}=\frac{\sigma{(n')}(1+p_1+p_1^2+\cdots+p_i^{a_i-1}+p_1^{a_1})}{(1+p_1+p_1^2+\cdots+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+\cdots+p_1^{a_1-1}+p_1^{a_1}$$

2. 否则 $n'\bmod p_1\not=0$：

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

$$\sigma{(n)}=\sigma{(n')}\times\sigma{(p_1)}$$

时间复杂度 $O(T+n)$，实际用时 $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 prime[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])
		{
			prime[++cnt]=i;
			num[i]=sigma[i]=i+1;
		}
		for(int j=1;j<=cnt;j++)
		{
			if(i*prime[j]>=N)break;
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)
			{
				num[i*prime[j]]=num[i]*prime[j]+1;
				sigma[i*prime[j]]=sigma[i]/num[i]*num[i*prime[j]];
				break;
			}
			num[i*prime[j]]=prime[j]+1;
			sigma[i*prime[j]]=sigma[i]*sigma[prime[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]?-1:ans[n])<<'\n';
	}
	return 0;
}