V 神玩游戏

Posted on Edited on In

题目大意：把一个数字拆成多个互质数的和，每次拆分之后将质数相乘起来得到一个数字，如果以前未曾出现过，则这次计数器增加

问计数器最终为多少

来自Ame__大佬的讲解：

1
2
3
4
5
6
7
解题思路:由唯一分解定理，任何一个数我们都可以拆成若干个质数相乘，题目要求的是将n分解成若干互质的数之和然后乘起来看有多少种不同的乘积，既然两两互质我们可以从互质出发，用质数来乘积最后。

那么我们将问题转化成了将n分解成多少不同质数的组合，注意这里的组合不仅含质数还有1，因为1与其他的数gcd$均为1，即互质。

那么我们设dp[i][j]表示从前i个质数里面组成和为j的组合的乘积数，考虑转移的话因为要求乘积不同的方案数，即求不同质数集合的方案数可知ans最多为不同的质数组合方案数个所以我们枚举的是质数的组合方案，这样保证了不同的乘积全都枚举到了，且只枚举了一次这样不会少枚举情况，因为枚举了所有的质数组合方案，所有的乘积都枚举到了。$dp[i][j]=\sum dp[i-1][j-k^p](p=0,1,2...)$

最后$ans=\sum_{i=0}^n dp[cnt][i]$，cnt为n以内质数的个数

代码如下：

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e3 + 6, G = 1e5 + 66;

int n, cnt, res;
int f[N][N], vis[N], pri[N];

inline void pres_dou(int lim)
{
    int i, j;
    for (i = 2; i <= lim; ++ i)
    {
        if (! vis[i]) pri[++ cnt] = i;
        for (j = 1; j <= cnt && i * pri[j] <= lim; ++ j)
        {
            vis[i * pri[j]] = 1;
            if (! (i % pri[j])) break;
        }
    }
    return;
}

signed main()
{
    int i, j;
    n = read(), pres_dou(n);

    f[0][0] = 1;
    for (i = 1; i <= cnt; ++ i)
    {
        for (j = 0; j <= n; ++ j)
        {
            f[i][j] = f[i - 1][j];
            int now = pri[i];
            for (; now <= j; now *= pri[i]) f[i][j] += f[i - 1][j - now];
        }
    }
    for (i = 0; i <= n; ++ i) res += f[cnt][i];
    put(res);
    
    return 0;
}