LZOI2021 题解

__cheems__ · 2023-07-11 10:42:38 · 个人记录

题意

将 n 分成 a_1+a_2+a_3+\cdots+a_m 且 a_1,a_2,a_3\cdots,a_m 均为质数。求 a 数组有多少种情况。

思路

先筛出 1\sim n 中的质数，用 a 数组存储。设 1\sim n 中质数个数为 k。随后使用完全背包的思路。即：

#include<bits/stdc++.h>
using namespace std;
int V,n;
int a[100001];
int dp[100001];
bool check(int x){
    for(int i=2;i*i<=x;i++){
        if(x%i==0) return 0;
    }
    return 1;
}
int main(){
    dp[0]=1;
    cin>>V;
    for(int i=2;i<=V;i++){
        if(check(i)){
            n++;
            a[n]=i;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=a[i];j<=V;j++){
            dp[j]+=dp[j-a[i]];
        }
    }
    cout<<dp[V]<<endl;
    return 0;
}