题解
timmark
·
·
题解
P4397 题解
一道有一定代码难度的数学题。
本题的关键在于求一个数的因子和。
我们先来看一个公式：
如果一个数 n 可以唯一分解为
n=p_1^{a_1}\times p_2^{a_2}\times\cdots\times p_k^{a_k}
则 n 的正因子个数等于
(a_1+1)(a_2+1)\cdots(a_k+1)
也可以写作
\prod \limits^{k}_{i=1} (a_i+1)
很好理解，乘法原理，每一个因子 p_i 都可以选择 0\sim a_i 中的任意次方。
接下来，是这道题的重点：
如果 n 可以唯一分解为上面的形式，则 n 所有的正因子的和等于
(1+p_1+{p_1}^2+\cdots+{p_1}^{a_1})(1+p_2+{p_2}^2+\cdots+{p_2}^{a_2})\cdots(1+p_k+{p_k}^2+\cdots+{p_k}^{a_k})
也可以写作
\prod \limits^{k}_{i=1} \sum \limits^{a_i}_{j=0} {p_i}^j
理解方法类似，读者自证不难。
那么，接下来，我们考虑这个问题怎么实现。
后文中为了简便，用 f(n,m) 表示 1+n+n^2+\cdots+n^m。
首先，处理出 \sqrt{N} 范围内的质数（其中 N 为 S 的最大值，本题中为 2\times 10^9）。
接下来，使用 dfs，记录 3 个参数，分别为：当前搜索到的质数编号 step、S 到目前剩余的部分 num、当前选择的每一个质数 p_i 的 f(p_i,j) 的乘积 now。初始时，step=1，num=S，now=1。
设当前质数为 p_{step}，枚举 j，如果 f(p_{step},j) 整除 num，则继续搜索，用 p_{step} 后面的质数 p_l，用 f(p_l,x) 来“拼出”\dfrac{num}{f(p_{step},j)}。
接下来考虑什么时候搜索停止，或者说记录答案。
显然，对于当 num=1 时，答案为 now，然后退出搜索。
还有其他情况吗？
如果只有上面这种情况，显然这个程序的复杂度是 \text O(S) 的，对于 S=2\times10^9 的情况显然会爆炸。
我们发现，f(n,m) 的增长速度极快，在 j=2 时就会达到 \text O(n^2) 级别。
所以，我们只需要考虑哪些满足 $p_i\le \sqrt{num}$ 的质数 $p_i$，然后对于 $num-1$ 是质数的情况记录答案 $now\times(num,-1)$ 即可（因为质数的因子只有 $1$ 和自身，所以因子和为自身 $+1$）。
本题还有一个坑，题目里没说清楚，那就是如果符合条件的答案不存在，只输出一行 $0$，不输出换行。
代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxm=1e6;
ll n,p[maxm],cp,cnt,ans[maxm];
bool np[maxm+5];
void gp(){//线性筛
for(int i=2;i<=maxm;i++){
if(!np[i]) p[++cp]=i;
for(int j=1;j<=cp;j++){
if(p[j]*i>maxm) break;
np[p[j]*i]=1;
if(i%p[j]==0) break;
}
}
}bool ip(ll num){//判断质数
if(num<=maxm) return np[num];//在线性筛范围内的直接返回
for(int i=2;i*1ll*i<=num;i++) if(num%i==0) return 1;//在线性筛范围外的根号复杂度判断
return 0;
}void dfs(ll num,ll step,ll now){
if(num==1){
ans[++cnt]=now;
return ;
}if(num>p[step] && !ip(num-1)) ans[++cnt]=now*(num-1);//非常重要，重点优化
for(int i=step;p[i]*p[i]<=num/*只到 num 的平方根*/;i++){
ll sum=p[i]+1,power=p[i];
for(int j=1;sum<=num;j++){
if(num%sum==0) dfs(num/sum,i+1,now*power);//整除的话继续搜
power*=p[i],sum+=power;
}
}
}signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
gp();
while(cin >> n ){
cnt=0;
dfs(n,1,1);
sort(ans+1,ans+cnt+1);//排序，答案可能无序
cout << cnt << "\n" ;
for(int i=1;i<=cnt;i++) cout << ans[i] << " " ;
if(cnt) cout << "\n" ;//坑
}return 0;
}
```
看到这里，点个赞吧。