Problem 77：Prime summations

題目鏈接：http://static.projecteuler.net/problem=77

題目大意：求最小的$n$，使得將$n$分解為若干個素數(shù)和的分解方法超過$5000$種.

二分+完全背包計數(shù)

設$n$的分解式的個數(shù)為$f(n)$，不難證明$f(n)$為單調(diào)函數(shù)，故若能較快求出$f(n)$則可用二分解.

直接分解求分解式的個數(shù)并不是很容易，考慮小于等于$n$的素數(shù)組合成$n$有多少種方案，于是問題就成了完全背包計數(shù)問題，求$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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/barrier/p/6573834.html

總結(jié)

以上是生活随笔為你收集整理的Problem 77：Prime summations的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。