Luogu

分析

你们这是什么输出格式啊,你们真是害人不浅啊你们这个输出格式!

$$ n=\prod_{i=1}^kp_i^{c_i} $$

$$ \mathbf{\sigma}(n)=\prod_{i=1}^k\left(\sum_{j=0}^{c_i}p_i\!^j\right) $$

搜索,对于每个 $p_i$ 枚举它的 $c_i$。注意到这里至多有一个 $p_i>\sqrt{S}$,因此我们只需要枚举 $\sqrt{S}$ 内的质数,再特殊处理剩下的那一个就好了。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000+10;

int v[N],p[N],cnt=0;
inline void sieve(int n) {
    for (re int i=2;i<=n;++i) {
        if (!v[i]) p[++cnt]=i;
        for (re int j=1;j<=cnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1;
            if (i%p[j]==0) break;
        }
    }
}

inline int isprime(int x) {
    if (x<2) return 0;
    for (re int i=2;i*i<=x;++i)
        if (x%i==0) return 0;
    return 1;
}

vector<int> ans;
inline void dfs(int S,int lst,int n) {
    if (S==1) { ans.push_back(n); return; }
    if (isprime(S-1)&&p[lst]<S-1) ans.push_back(n*(S-1));
    for (re int i=lst+1;i<=cnt&&p[i]*p[i]<=S;++i)
        for (re int s=1+p[i],t=p[i];s<=S;t*=p[i],s+=t)
            if (S%s==0) dfs(S/s,i,n*t);
}

int main() { sieve(50000); int S;
    while (scanf("%d",&S)==1) {
        ans.clear(); dfs(S,0,1);
        sort(ans.begin(),ans.end());
        printf("%lu\n",ans.size());
        // 注意答案为 0 时不要再输出一个空行!
        for (re int i:ans) printf("%d%c",i," \n"[i==ans.back()]);
    }
    return 0;
}
最后修改:2019 年 10 月 28 日 08 : 22 PM