解题思路:另数组全部为0,能够装出来的设为1(遍历大数组,不停的往后迭代,若b[i-a[j]]不是0,即可赋值,具体如下),最后数数
注意事项:判断公约数 哦
参考代码:
#include <iostream>
using namespace std;
#define N 100000
int a[100]={0},b[N]={0};
int gy(int a,int b)//判断公约数
{
while(a%b!=0)
{
int c=a%b;
a=b;
b=c;
}
return b;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
if(n==1)//判断n=1
{
if(a[0]!=1) cout<<"INF"<<endl;
else cout<<0<<endl;
return 0;
}
int gys=a[0];
for(int i=1;i<n;i++)
{
gys=gy(gys,a[i]);
}
if(gys!=1)//公约数不为1,直接输出无限
{
cout<<"INF"<<endl;
return 0;
}
b[0]=1;
for(int j=0;j<n;j++)//核心代码
{
for(int i=a[j];i<N;i++)
{
if(b[i-a[j]]) b[i]=1;//不停的往后迭代,若b[i-a[j]]不是0,即可赋值
}
}
int sum=0;
for(int i=1;i<N;i++)//数0
{
if(b[i]==0)
sum++;
}
cout<<sum<<endl;
return 0;
}
0.0分
0 人评分
三进制小数 (C++代码)(第11位大于1.5才能进位)浏览:1151 |
简单的a+b (C语言代码)浏览:494 |
C语言考试练习题_一元二次方程 (C语言代码)浏览:737 |
时间转换 (Java代码)浏览:575 |
【明明的随机数】 (C++代码)浏览:781 |
神奇的fans (C语言代码)浏览:988 |
C语言程序设计教程(第三版)课后习题8.6 (C语言代码)浏览:585 |
A+B for Input-Output Practice (II) (C语言代码)浏览:601 |
快速排序算法1浏览:885 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:1189 |