题意:
若 $a_1+a_2+\cdots+a_h=n$(任意 h<=n), 求 $lcm(a_i)$ 的种类数
思路:
设 $lcm(a_i)=x$,
由唯一分解定理,$x=p_1^{m_1}+p_2^{m_2}+\cdots+p_{tot}^{m_{tot}}$
设 $b_i=p_i^{m_i}$,
则能组成 x 的和最小的数为 $\sum p_i^{m_i}$
所以只要 $\sum p_i^{m_i}\leq n$ 即可,
其中小于的时候, 剩余补 1 即可
dp[i][j] 表示选了前 i 个素数, 他们的和为 j 时的方法数
代码:
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cmath>
- #include<cstring>
- #include<string>
- #include<stack>
- #include<queue>
- #include<deque>
- #include<set>
- #include<vector>
- #include<map>
- #include<functional>
- #define fst first
- #define sc second
- #define pb push_back
- #define mem(a,b) memset(a,b,sizeof(a))
- #define lson l,mid,root<<1
- #define rson mid+1,r,root<<1|1
- #define lc root<<1
- #define rc root<<1|1
- #define lowbit(x) ((x)&(-x))
- using namespace std;
- typedef double db;
- typedef long double ldb;
- typedef long long ll;
- typedef unsigned long long ull;
- typedef pair<int,int> PI;
- typedef pair<ll,ll> PLL;
- const db eps = 1e-6;
- const int mod = 1e9+7;
- const int maxn = 2e3+100;
- const int maxm = 2e6+100;
- const int inf = 0x3f3f3f3f;
- const db pi = acos(-1.0);
- int n, tot;
- int prime[1000 + 10];
- int vis[1000 + 10];
- ll ans, dp[1000 +10][1000 + 10];
- int main(){
- scanf("%d", &n);
- tot = 0;
- for(int i = 2; i <= 1000; i++){
- if(!vis[i])prime[++tot] = i;
- for(int j = 1; j <= tot && i *prime[j] <= 1000; j++){
- vis[i*prime[j]] = 1;
- if(i%prime[j]==0)break;
- }
- }
- dp[0][0] = 1;
- for(int i = 1; i <= tot; i++){
- for(int j = 0; j <= n; j++)dp[i][j] = dp[i-1][j];
- for(int j = prime[i]; j <= n; j *= prime[i]){
- for(int k = 0; k + j <= n; k++){
- dp[i][k+j] += dp[i-1][k];
- }
- }
- }
- ans = 0;
- for(int i = 0; i <= n; i++)ans+=dp[tot][i];
- printf("%lld", ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2833560.html