这题我必不可能超时

发表于 | 更新于 | 阅读次数：

=_= 一个题如果一直超时，要考虑是不是有很多重复的计算。
POJ-2992

题意

计算组合数的因子个数。(0 ≤ k ≤ n ≤ 431)

分析

显然，我们不能算出组合数再求因子个数。求N的因子个数，可以将N分解质因数，每个质因子的数量A_i先+1，然后将所有A_i相乘，就是因子个数。别问，问就是不会证+_+
这个题目的查询蛮多的，打表不打表，差距不大。关键上述做法的实现是否够快

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
#include <stdio.h>
using namespace std;
#define endl '\n'
typedef long long ll;
int p[83] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431 };
ll ans[432][432];
int in[432][432];//in[i][j]为i阶乘的因子j的数量
void Pre(int x)
{
    int i = 0, x0 = x;
    for (int j = 0; j < 83; ++j) {
        in[x][p[j]] = in[x - 1][p[j]];//阶乘嘛，必须带上前一个数的因子
    }
    while (i < 83) {
        if (x % p[i] != 0)
            ++i;
        else {
            x /= p[i];
            ++in[x0][p[i]];
        }
    }
}
int main()
{
    int n, k;
    for (int i = 2; i < 432; ++i) {
        Pre(i);
    }
    for (n = 0; n < 432; ++n) {
        int n0 = n / 2;
        for (k = 0; k <= n0; ++k) {
            int ma[432];
            ans[n][k] = 1;
            for (int i = 0; i < 83; ++i) {
                ma[p[i]] = in[n][p[i]] - in[k][p[i]] - in[n - k][p[i]];//公式中的除法，转变成因子数量的减法
                ans[n][k] *= ma[p[i]] + 1;
            }
            ans[n][n - k] = ans[n][k];//众所周知，ans[10][4]和ans[10][6]相等
        }
    }
    while (scanf("%d%d", &n, &k) != EOF)
        printf("%lld\n", ans[n][k]);

    return 0;
}
0%