題目：http://acm.zju.edu.cn/changsha/showProblem.do?problemId=28

?

題意：給一個數n，范圍是[2,80000]，使用加，乘運算和最多3個素數，有多少種方法使得結果恰好等于n。

?

分析：先素數篩選，然后我們可以看出，設有3個素數a，b，c，那么有如下幾種情況。

a + b + c = n;

a + b = n;

a + b*c = n;

a*b = n;

a*b*c = n;

a = n;

?

那么我們可以用背包的思想來預處理，然后詢問即可。

?

#include <iostream> #include <string.h> #include <stdio.h>using namespace std; const int N = 80005; const int MOD = 1000000007; bool prime[N]; int p[N],cnt;int dp1[N][4],dp2[N][4];void isprime() {cnt = 0;int i,j;memset(prime,true,sizeof(prime));for(i=2;i<N;i++){if(prime[i]){p[cnt++] = i;for(j=i+i;j<N;j+=i){prime[j]=false;}}} }void Work() {dp1[0][0] = 1;dp2[1][0] = 1;for(int i=0; i<cnt; i++){for(int j=0; j<N&&p[i]+j<N; j++){for(int k=0; k<=2; k++)dp1[j+p[i]][k+1] = (dp1[j+p[i]][k+1] + dp1[j][k]) % MOD;}}for(int i=0; i<cnt; i++){for(int j=0; j<N && p[i]*j<N; j++){for(int k=0; k<=2; k++)dp2[j*p[i]][k+1] = (dp2[j*p[i]][k+1] + dp2[j][k]) % MOD;}}for(int i=0; i<cnt; i++){for(int j=0; j<N&&j+p[i]<N; j++)dp1[j+p[i]][3] = (dp1[j+p[i]][3] + dp2[j][2]) % MOD;} }int main() {isprime();Work();int n;while(~scanf("%d",&n)){int ans = 0;for(int i=1; i<=3; i++){ans = (ans+dp1[n][i]) % MOD;if (i != 1)ans = (ans+dp2[n][i]) % MOD;}printf("%d\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的2013年长沙网络赛G题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。