聪明的燕姿

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1973 字
给定S，求所有满足σ=S的正整数n，升序输出
一本通
练习
正文

/*
原题：T1629「一本通 6.3 练习 2」聪明的燕姿
题意：给定 S，求所有满足 σ(n)=S（n 的所有正约数之和等于 S）的正整数 n，升序输出。
思路：n=Πp_i^{e_i}，σ(n)=Π(1+p_i+...+p_i^{e_i})。DFS 按递增素数枚举每个素数的指数，整除剪枝，
      剩余值若为 (大素数+1) 则收尾。用 set 去重并按升序收集。
复杂度：时间 O(可行分解数，极小) / 空间 O(素数表+答案数)
易错点：素数只需筛到 √S_max 即可，更大的素数只可能以单素数(p=left-1)形式收尾；答案用 set 去重。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int PMAX=50000;
vector<int> primes;
set<ll> res;
bool isp(int x){
    if(x<2) return false;
    for(int p:primes){
        if((ll)p*p>x) break;
        if(x%p==0) return false;
    }
    return true;
}
// now:当前已乘得的 n 前缀；left:剩余待凑的 σ 乘积；last:上一个使用的素数
void dfs(ll now, ll left, ll last){
    if(left==1){
        res.insert(now);
        return;
    }
    // 剩余整体是一个素数 p 的 σ(p)=p+1，即 p=left-1
    if(left-1>last && isp((int)(left-1))){
        res.insert(now*(left-1));
    }
    for(int p:primes){
        if(p<=last) continue;
        if((ll)p+1>left) break;
        ll s=1, pe=1;
        while(true){
            pe*=p;
            s+=pe;
            if(s>left) break;
            if(left%s==0) dfs(now*pe, left/s, p);
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    vector<char> iscomp(PMAX+1, 0);
    for(int i=2;i<=PMAX;i++){
        if(!iscomp[i]){
            primes.push_back(i);
            for(long long j=(ll)i*i;j<=PMAX;j+=i) iscomp[j]=1;
        }
    }
    vector<ll> nums;
    ll tmp;
    while(cin>>tmp) nums.push_back(tmp);
    int start=0, cnt=0;
    // 若首个数恰等于后续个数，则视为 k 组数据；否则每个数各自一组（兼容样例单组）
    if(!nums.empty() && nums[0]==(ll)nums.size()-1){
        start=1;
        cnt=(int)nums.size()-1;
    }else{
        start=0;
        cnt=(int)nums.size();
    }
    for(int i=start;i<start+cnt;i++){
        res.clear();
        dfs(1, nums[i], 1);
        cout<<res.size()<<"\n";
        bool first=true;
        for(ll v:res){
            if(!first) cout<<" ";
            cout<<v;
            first=false;
        }
        cout<<"\n";
    }
    return 0;
}
聪明的燕姿

正文

一本通·提高篇的其它内容
