Problem 77：Prime summations

题目链接：http://static.projecteuler.net/problem=77

题目大意：求最小的$n$，使得将$n$分解为若干个素数和的分解方法超过$5000$种.

二分+完全背包计数

设$n$的分解式的个数为$f(n)$，不难证明$f(n)$为单调函数，故若能较快求出$f(n)$则可用二分解.

直接分解求分解式的个数并不是很容易，考虑小于等于$n$的素数组合成$n$有多少种方案，于是问题就成了完全背包计数问题，求$f(n)$的复杂度为$O(frac{n^2}{logn})$.

总复杂度为$O(n^2)$.

代码如下：

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #define N 100005
 5 using namespace std;
 6 bool vis[N];
 7 typedef long long ll;
 8 ll p[N],k,dp[N];
 9 void prime(){
10     for(ll i=2;i<N;++i){
11         if(!vis[i])p[k++]=i;
12         for(ll j=0;j<k&&p[j]*i<N;++j){
13             vis[p[j]*i]=1;
14             if(i%p[j]==0)break;
15         }
16     }
17 }
18 ll check(ll n){
19     memset(dp,0,sizeof(dp));dp[0]=1;
20     for(ll i=0;i<k&&p[i]<=n;++i)
21         for(ll j=p[i];j<=n;++j)
22             dp[j]+=dp[j-p[i]];
23     return dp[n];
24 }
25 int main(void){
26     prime();
27     ll l=1,r=500;
28     while(l<=r){
29         ll mid=(l+r)/2;
30         if(check(mid)>5000)r=mid-1;
31         else l=mid+1;
32     }
33     cout<<l;
34 }