P5697 题解

ikunTLE · 2024-06-11 21:33:57 · 题解

题目传送门

思路

本题是一道搜索。

分析过样例后，你会发现从上一次搜下来的数，一直到 \sqrt{n} 中，所有 n\div i 的质因子都接着往下搜，每一个新的质因子就是一个答案。既然那个数是 n 的质因数了，答案就是计数器 +n-1（这里的 n 是更新后每一次的 n\div i）。

经过排序后就是我们要的答案。

AC CODE

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,ans[N],num;
map<int,bool>mp;
void dfs(int p,int x,int cnt){
    if(x<=p){//没超出答案范围
        int temp=cnt+p-1;
        if(!mp[temp]){//去重
            ans[++num]=temp;
            mp[temp]=true;
        }
    }
    int sqrt_p=sqrt(p);
    for(int i=x;i<=sqrt_p;++i)
        if(!(p%i))//是p（n÷i）的质因子
            dfs(p/i,i,cnt+i-1);//接着搜
    return;
}
int main(){
    scanf("%d",&n);
    dfs(n,2,0);//2是最小的质数，故从2开始
    printf("%d\n",num);
    sort(ans+1,ans+num+1);//排序
    for(int i=1;i<=num;++i)
        printf("%d ",ans[i]);
    return 0;
}