bzoj3629

dfs

跟上道题很像有木有

同样地，我们暴力枚举约数

根据约数和公式，得出$S=\prod_{i=1}^{n}{(1+p+p^{2}+...+p^{a_{i}})}$

所以每次我们暴力枚举是哪个约数，次数是多少，然后爆搜

如果剩下的约数和$S-1$是质数，那么说明约数只剩下一个大质数，直接统计答案结束即可

因为一个数不可能大于自己的约数和，所以大于$sqrt(S)$的约数只能有一个

#include<bits/stdc++.h>

using namespace std;

const int N = 5e4 + ;

int s, sqrts;

int p[N], mark[N], ans[N << ];

void shaker() {

    for(int i = ; i < N; ++i) {

        if(!mark[i]) {

            p[++p[]] = i;

        }

        for(int j = ; j <= p[] && i * p[j] < N; ++j) {

            mark[i * p[j]] = ;

            if(i % p[j] == ) {

                break;

            }

        }

    }

}

bool judge(int x) {

    if(x == ) {

        return ;

    }

    if(x < N) {

        return !mark[x];

    }

    for(int i = ; p[i] * p[i] <= x; ++i) {

        if(x % p[i] == ) {

            return ;

        }

    }

    return ;

}

void dfs(int last, int tot, int sum) {

    if(tot == ) {

        ans[++ans[]] = sum;

        return;

    }

    if(tot -  > sqrts && judge(tot - )) {

        ans[++ans[]] = sum * (tot - );

    }

    for(int i = last + ; p[i] <= sqrts; ++i) {

        int t = p[i], all = ;

        for(int j = ; all + t <= tot; ++j) {

            all += t;

            if(tot % all == ) {

                dfs(i, tot / all, sum * t);

            }

            t *= p[i];

        }

    }

}

int main() {

    shaker();

    while(scanf("%d", &s) != EOF) {

        ans[] = ;

        sqrts = sqrt(s);

        dfs(, s, );

        sort(ans + , ans + ans[] + );

        printf("%d\n", ans[]);

        for(int i = ; i < ans[]; ++i) {

            printf("%d ", ans[i]);

        }

        if(ans[]) {

            printf("%d\n", ans[ans[]]);

        }

    }

    return ;

}

巴特西

bzoj3629

最新文章

热门文章