聪明的燕姿

发表于 | 更新于
本文字数： 3.4k | 阅读时长 ≈ 3 分钟

$Smart$ $Yanzi$

$Description$

给你一个数 $S$ ，求有多少数的约数和等于 $S$ 。

$Solution$

对于一个数 $S$ ，根据算数基本定理，有分解式：
$$
S = p_1^{a_1}p_2^{a_2}p_3^{a_3}…p_n^{a_n}
$$
所以约数和就是
$$
sum = \prod_{i = 1}^{n}\sum_{j=0}^{a_i}p_i^j
$$
由于 $S<=2*10^9$ ，考虑枚举 $S$ 的所有因子，先筛出 $\sqrt{S}$ 以内的质数，然后枚举 $p_i$ ，对于每个 $p_i$ 枚举 $a_i$ ，爆搜，如果将 $S$ 分解成功，答案 $ + 1$ 。

同时，如果 $S - 1$ 是一个质数，且 $>=$ 当前搜的 $p_i$ ，答案也要 $ + 1$ ，因为 $S - 1$ 也是此时构造出的数的因子。

其实我们是先把质因子全部取出来，然后找所有的乘起来的可能，对于每种可能都枚举它是否成立。

就是把 $S$ 拆掉，然后再拼回去。

$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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include<bits/stdc++.h>
//#include<tr1/unordered_map>
//#include"Bignum/bignum.h"
//#define lll bignum
#define ls(x) ( x << 1 )
#define rs(x) ( x << 1 | 1 )
//#define mid ( ( l + r ) >> 1 )
#define lowbit(x) ( x & -x )
#define debug(x) cout << "#x = " << x << endl
#define re register
#define For(i, j, k) for(re int i = (j); i <= (k); i++)
#define foR(i, j, k) for(re int i = (j); i >= (k); i--)
#define Cross(i, j, k) for(re int i = (j); i; i = (k))
using namespace std;
typedef long long ll;
const ll N = 100011;
const ll inf = 0x3f3f3f3f3f3f;

ll S, tot = 0, di[N << 2];

namespace IO {

    inline ll read() {
        ll x = 0; bool f = 0; char ch = getchar();
        for (; !isdigit (ch); ch = getchar()) f^= (ch == '-');
        for (; isdigit (ch); ch = getchar()) x = ( x << 3 ) + ( x << 1 ) + ( ch ^ 48 );
        return f? -x: x;
    }

    inline void write( ll x ) {
        if ( x < 0 ) putchar ( '-' ), x = -x;
        if ( x > 9 ) write ( x / 10 );
        putchar ( x % 10 | 48 );
    }

    inline void wrn ( ll x ) { write (x); putchar ( ' ' ); }

    inline void wln ( ll x ) { write (x); putchar ( '\n' ); }

    inline void wlnn ( ll x, ll y ) { wrn (x), wln (y); }

}

using namespace IO;

ll cnt, pr[N], vis[N];

inline void Init () {
    For ( i, 2, N ) {
        if ( !vis[i] ) pr[++cnt] = i;
        for ( re int j = 1; j <= cnt && i * pr[j] <= N; j++ ) {
            vis[i * pr[j]] = 1;
            if ( i % pr[j] == 0 ) break;
        }
    }
} // 预处理质数。 

inline bool check ( ll n ) {
    if ( n == 1 ) return 0;
    if ( n <= N ) return !vis[n];
    for ( re int i = 1; pr[i] * pr[i] <= n; i++ )
        if ( n % pr[i] == 0 ) return 0;
    return 1;
} // 判断质数。 

inline void dfs ( ll now, ll x, ll y ) { // x 表示当前用到第几个质数，y 表示当前搜出的数。
    if ( now == 1 ) { di[++tot] = y; return ; } // 满足答案。
    if ( now - 1 >= pr[x] && check ( now - 1 ) ) di[++tot] = y * ( now - 1 );
    /* 
        如果当前数能表示成一个质数加一与一的乘积，那么就会是答案，只需要将
        当前算出的答案乘上它就是满足条件的答案。
    */ 
    ll p, temp;
    for ( re int i = x; pr[i] * pr[i] <= now; i++ ) {
        temp = pr[i], p = pr[i] + 1;
        for (; p <= now; temp *= pr[i], p += temp)
            if ( now % p == 0 ) dfs ( now / p, i + 1, y * temp );
    } // 枚举符合题意的因子。
}

int main() {
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
    Init ();
    while ( cin >> S ) {
        tot = 0; memset ( di, 0, sizeof ( di ) );
        dfs ( S, 1ll, 1ll ); sort ( di + 1, di + tot + 1 ); // 从小到大输出。 
        wln (tot); For ( i, 1, tot - 1 ) wrn ( di[i] ); if (tot) wln ( di[tot] );
    } return 0;
}

/*
42

20 26 41
*/

题目链接