[NOIP2002 普及组] 选数
洛谷传送门
点击查看题目
题目描述
已知 n 个整数 x1,x2,…..,xn,以及 1 个整数 k(k
3+7+12=22
3+7+19=29
7+12+19=38
3+12+19=34
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数:3+7+19=29。
输入格式
第一行两个空格隔开的整数 n,k(1 le n le 20,k
第二行 n 个整数,分别为 x_1,x_2,cdots,x_n(1 le x_i le 5times 10^6)。
输出格式
输出一个整数,表示种类数。
样例 #1
样例输入 #1
4 3
3 7 12 19
样例输出 #1
1
提示
【题目来源】
NOIP 2002 普及组第二题
代码中的sqrt(x)的用处:举个例子,9,sqrt(9)=3,所以9可以分解为19或33,一旦越过了3(sqrt(9)),那么之后的分解方式比与先前的分解方式重复(9*1),这个还是需要自己理解理解。for循环从2到sqrt(x)的好处就是可以简化程序的时间复杂度。
#include //引入头文件
using namespace std;
int n,k,a[21],s=0,ans=0;//定义全局变量,方便写函数
bool f[21];//判断该数有没有被选过,用bool型变量
int ss(int x)//定义判断素数的函数
{
if(x==1||x==0)return 0;//考虑特殊情况(虽然和为1或0不太可能,但还是要预防一下极品数据)
for(int i=2;i> n >> k;//读入共有几个数和每次选几个数
for(int i=1;i> a[i];//读入每个数的值
f[i]=true;//将判断该数选没选过的bool型数组初始化
}
xs(1,1);//开始调用选数函数
cout
服务器租用托管,机房租用托管,主机租用托管,https://www.e1idc.com