欧几里得算法的应用

题目描述

标题：包子凑数

小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。

每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

输入

第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)  

输出

一个整数代表答案。如果凑不出的数目有无限多个，输出INF。

例如，
输入：

样例

2  
4  
5   

输出

6

再例如，
输入：

2
4
6

输出

INF

样例解释：
对于样例1，凑不出的数目包括：1, 2, 3, 6, 7, 11。
对于样例2，所有奇数都凑不出来，所以有无限多个。

算法1

欧几里得算法

思路：用欧几里得来判断输入的数是否都不互质，如果都不互质则不能凑出的数有无限个，输出INF，欧几里得辗转相除法来求两个数是否互质。对于可以凑出有限多个数的组合，利用动态规划来标记可以被组成的数，记为1；

C++ 代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<stdio.h>
using namespace std;
const int N = 10010; //一共有10000个包子左右
int a[N];
bool f[N];  //记录可以被组合的包子
int n;
int gcd(int a,int b){
    //(a,0)的最小公约数是a
    return b ? gcd(b,a % b) : a;
}

int main(){
    int g = 0,res = 0;
    f[0] = true;
    cin >> n;
    for(int i = 0;i < n;++i){
        cin >> a[i];
        //求输入的所有数的最小公约数
        if(i == 0) g = a[i];
        else g = gcd(g,a[i]); //只要出现一个互质的数(g = 1),那么接下来得到的g都会是1，因为g(1,xxx)得到的最小公约数都是1
        for(int j = 0;j < 10000;++j){  //遍历所有包子可能的个数，对于已经能组合的包子个数加上a[i](初始时只有f[0 + a[i]]是可以组合的)
            if(f[j]) f[j + a[i]] = true;  
        }
    }
    if(g != 1){  //如果一个互质的数都没有那么有无限个无法凑出来的数
        puts("INF");
        return 0;
    }else{
        for(int i = 0;i < 10000;++i){
            if(!f[i]) res++;
        }
        cout << res << endl;
    }
    return 0;
}