题解：P4397 [JLOI2014] 聪明的燕姿

· · 题解

题意

给定 S，求所有正约数之和等于 S 的正整数

前置知识

唯一分解：n=p_1^{q_1}\times p_2^{q_2}\times\cdots\times p_k^{q_k}

因数和公式：记 f(n) 为 n 所有正因子的和，则有：

f(n)=(1+p_1+{p_1}^2+\cdots+{p_1}^{q_1})(1+p_2+{p_2}^2+\cdots+{p_2}^{q_2})\cdots(1+p_k+{p_k}^2+\cdots+{p_k}^{q_k})

可以通过乘法原理证明。

算法

核心为 dfs。

枚举 {p_k} 和 {q_k}，若满足

S=(1+p_1+{p_1}^2+\cdots+{p_1}^{q_1})(1+p_2+{p_2}^2+\cdots+{p_2}^{q_2})\cdots(1+p_k+{p_k}^2+\cdots+{p_k}^{q_k})

那么将 p_1^{q_1}\times p_2^{q_2}\times\cdots\times p_k^{q_k} 作为答案存储。

接下来考虑剪枝。

对 {q_k} 的大小进行分类讨论：

1. 当 {q_k}=1：

用 x 表示当前正在拆分的数，如果 (x-1) 为质数，因为质数无法再分为质数的乘积，所以当且仅当新的 {p_k}=x-1,{q_k}=1 时可以得到一组新的解。

2. 当 {q_k}>1：

只需要枚举不大于 \sqrt x 的质数即可，这些质数可以预处理。

AC code

#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define fir first
#define sec second
#define ctn continue
#define pb push_back
#define ll long long
#define recal(x) x.resize(x.size()-1)//用来回溯 
int n;
vector<int>ans,prinum;//prinum存储sqrt(s)范围内的质数 
vector<pair<int,int> >ch;//记录已拆分的部分，first为底数p，second为指数q 
bool pri(int x) {
    rep(i,2,sqrt(x)) {
        if(x%i==0)return 0;
    }
    return x>1;//1不是质数 
}
void ini() {
    ans.clear();
}
void dfs(int x,int lst,ll pd) {//x表示当前正在拆分的数，lst表示上一次使用的数在prinum[]数组中的下标，pd表示已确定部分的乘积 
    if(x==1||pri(x-1)&&(lst<0||x-1>prinum[lst])) {
        //x==1表示拆分完毕，特判x-1为质数的情况，但要保证x-1大于上一次选取的数，以免产生重复解 
        if(x>1)ans.pb(pd*(x-1));//注意这只是一种方案，不能返回 
        else {
            ans.pb(pd);
            return;
        }
    }
    for(int i=lst+1; prinum[i]<=sqrt(x); i++) {//i枚举用来拆分的质数，从prinum中选取 
        ll sum=1,pow1=prinum[i];//sum记录(p^0+p^1+...+p^j)的值 
        for(int j=1;; j++) {//枚举次数 
            sum+=pow1;
            pow1*=prinum[i];
            if(sum>x)break;//超出退出 
            if(x%sum)ctn;//保证整除 
            ch.pb({prinum[i],j});//记录答案 
            dfs(x/sum,i,pd*pow1/prinum[i]);//pow1多乘了一次，退回去 
            recal(ch);
        }
    }
}
const int MAX=45000;//sqrt(2e9)<45000 
bool ispri[MAX+1];
void getpri() {//筛法求质数 
    rep(i,2,MAX) {
        if(ispri[i]==0) {
            for(int j=2; i*j<=MAX; j++)ispri[i*j]=1;
            prinum.pb(i);//顺便记录 
        }
    }
}
int main() {
    getpri();
    while(cin>>n) {
        ini();
        dfs(n,-1,1);//注意lst初值为-1 
        cout<<ans.size()<<'\n';
        if(ans.size()==0)ctn;//避免无解时输出多余换行 
        sort(ans.begin(),ans.end());//题目要求升序输出 
        for(int i:ans)cout<<i<<' ';
        cout<<'\n';
    }
}