本文共 471 字，大约阅读时间需要 1 分钟。
由扩展欧几里得知：ax+by=gcd(x,y) 这个方程一定有解
我们这个题目要求a和b都大于等于0，且x，y也都大于0 所以如果gcd（x，y）等于1时，我们可以左右两边同时 乘以一个数，这样就能凑出任意数。也就是当所有组合 的gcd如果都不为1时，输出INF，否则根据完全背包求 解答案。代码如下：
#includeusing namespace std;int n;int dp[10007],a[107];int main(){ int flag=0; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } int g=a[1]; for(int i = 2; i <= n; i++){ g=__gcd(g, a[i]); if(g==1) flag=1;//a1*x1+a2*x2+...+an*xn=gcd(a1,a2,...an) } if(!flag) cout<<"INF"<
转载地址：http://bsgwi.baihongyu.com/