BZOJ 3629: [JLOI2014]聪明的燕姿

Description

给出一个数S,求所有的x,满足x的约数和等于S,100组数据

Input

输入包含k组数据(k<=100)对于每组数据,输入包含一个数S

Output

对于每组数据,输出有两行,第一行包含一个整数m,表示有m个等的人,第二行包含相应的m个数,表示所有等的人的号码牌,行末无空格。注意:你输出的号码牌必须按照升序排列。
如果m=0,则不需要空行。

Sample Input

42

Sample Output

3
20 26 41

HINT

对于100%的数据,有 \(S \le 2*10^9\)

Solution

先想如何求一个数x的约数和?

将x分解,\(x=\prod_i p_i^{k_i}\),那么对于每一个\(p_i\)构造函数 \( f(i) = \sum_{0 \le j \le k_i} p_i^{j} \),答案就是 \(\prod_i f(i)\)。
因为一个数可以分解出很少的数量的质因数,我们就可以dfs了。
在dfs的过程中注意剪枝,然后对于一定无解的情况判掉。

我的代码跑得比较慢,可能是因为太弱了吧!(>_<)~~

Code

#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;
typedef long long LL;
const int Ni = 44721;
const int maxn = Ni + 2;
const LL N = Ni;
int cnt, tot;
bool vis[maxn];
LL n, p[maxn], dst[maxn];
inline LL ksm(LL a, LL b, LL c) {
    LL ret = 1ll, tmp = a % c;
    while (b) {
        if (b & 1ll) ret = (ret * tmp) % c;
        tmp = (tmp * tmp) % c;
        b >>= 1ll;
    }
    return ret;
}
inline LL gr(LL x) {
    LL ret;
    for (int i = 0; i < 4; ++i) ret ^= rand() << (16 * i);
    if (ret < 0) ret = -ret;
    return ret % (x - 2ll) + 2ll;
}
inline bool isprime(LL x) {
    for (int k = 0; k < 4; ++k)
        if (ksm(gr(x), x - 1ll, x) != 1ll)
            return false;
    return true;
}
inline void shake() {
    for (int i = 2; i <= Ni; ++i) {
        if (!vis[i]) p[cnt++] = i;
        for (int j = 0; j < cnt; ++j) {
            if (p[j] * LL(i) > N) break;
            vis[p[j] * i] = true;
        }
    }
}
inline LL sqr(LL x) { return x * x; }
void dfs(int now, LL cur, LL left) {
    if (left == 1ll) {
        dst[tot++] = cur;
        return;
    }
    if (sqr(left - 1ll) >= n && isprime(left - 1ll)) dst[tot++] = cur * (left - 1ll);
    LL tmp, sum; int i;
    for (i = now; p[i] <= left && p[i] * p[i] <= n; ++i) {
        tmp = p[i]; sum = tmp + 1ll;
        while (sum <= left) {
            if (left % sum == 0) dfs(i + 1, cur * tmp, left / sum);
            tmp *= p[i];
            sum += tmp;
        }
    }
}
int main() {
    srand(20000926); shake(); p[cnt] = 1000000007;
    while (scanf("%lld", &n) == 1) {
        tot = 0; dfs(0, 1ll, n);
        sort(dst, dst + tot);
        tot = unique(dst, dst + tot) - dst;
        printf("%d\n", tot);
        if (tot != 0) {
            printf("%lld", dst[0]); for (int i = 1; i < tot; ++i) printf(" %lld", dst[i]);
            putchar('\n');
        }
    }
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据