若给的数之间不存在互质的数,则不能表示的数为无限;
找出乘积最小的一组互质的数a,b,则用a,b最大不能被表示的数为a*b-a-b;
在1~a*b-a-b范围内找出不能表示的数,方法:从1开始,若i能被表示,则i+给定的数可以被表示。
(代码略冗长)
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
int a[101];
int is[10000];
int n,i,j,s=0,ans=0;
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
int main(){
cin>>n;
for(i=0;i<n;i++)cin>>a[i];
sort(a,a+n);
if(a[0]==1){ //若存在1,答案为0
cout<<0;
return 0;
}
for( i=0;i<n;i++){ //判断给定数是否存在互质
for( j=i+1;j<n;j++){
if(gcd(a[i],a[j])==1){
s++;
break;
}
}
}
if(s==0){ //无互质输出INF
cout<<"INF";
return 0;
}
for( i=0,s=0;i<n;i++){ //找出最小的互质数
for( j=i+1;j<n;j++){
if(gcd(a[i],a[j])==1){
s++;
break;
}
}
if(s>0)break;
}
int max=a[i]*a[j]-a[i]-a[j]; //max是用a[i]a[j]最大不能表示的数
for(i=0;i<n;i++){
is[a[i]]=1;
}
for(i=1;i<=max;i++){ //缩小范围后找出答案
if(is[i]==0)ans++;
else{
for(j=0;j<n;j++){
is[i+a[j]]=1;
}
}
}
cout<<ans;
return 0;
}