企业官网建设流程全解析

题目：P1832 A+B Problem（再升级）

题目背景

题目名称是吸引你点进来的。

实际上该题还是很水的。

题目描述

• 1 + 1 = ? 1+1=?1+1=?显然是2 22。
• a + b = ? a+b=?a+b=?P1001 回看不谢。
• 哥德巴赫猜想 似乎已呈泛滥趋势。

以上纯属个人吐槽

给定一个正整数n nn，求将其分解成若干个素数之和的方案总数。

输入格式

一行一个正整数n nn。

输出格式

一行一个整数表示方案总数。

输入输出样例 #1

输入 #1

7

输出 #1

3

输入输出样例 #2

输入 #2

20

输出 #2

26

说明/提示

样例解释

存在如下三种方案：

• 7 = 7 7=77=7。
• 7 = 2 + 5 7=2+57=2+5。
• 7 = 2 + 2 + 3 7=2+2+37=2+2+3。

数据范围及约定

• 对于30 % 30\%30%的数据1 ≤ n ≤ 10 1\le n\le 101≤n≤10。
• 对于100 % 100\%100%的数据，1 ≤ n ≤ 10 3 1\le n\le 10^31≤n≤103。

代码（一维数组）

#include<bits/stdc++.h>usingnamespacestd;constintN=1e3+10;longlongV,n,cnt,v[N],f[N];boolisprime(intx){for(inti=2;i<=x/i;i++)if(x%i==0)returnfalse;returntrue;}intmain(){cin>>V;for(inti=2;i<=V;i++){if(isprime(i)){cnt++;v[cnt]=i;}}n=cnt;f[0]=1;for(inti=1;i<=n;i++)for(intj=v[i];j<=V;j++)f[j]+=f[j-v[i]];cout<<f[V];return0;}

结果