OI

BZOJ 3629: [JLOI2014]聪明的燕姿

Description

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

Input

输入包含k组数据（k<=100）对于每组数据，输入包含一个数S

Output

对于每组数据，输出有两行，第一行包含一个整数m，表示有m个等的人，第二行包含相应的m个数，表示所有等的人的号码牌，行末无空格。注意：你输出的号码牌必须按照升序排列。

如果m=0，则不需要空行。

Sample Input

1

42

Sample Output

1
2

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

#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');
        }
    }
}