小猴编程C++ | 分蛋糕

学习C++从娃娃抓起！记录下在学而思小猴编程学习过程中的题目，记录每一个瞬间。侵权即删，谢谢支持！

附上汇总贴：小猴编程C++ | 汇总-CSDN博客

---

【题目描述】

小A有n种蛋糕，编号为1~n，第i种蛋糕有ai个。

小A现在希望把这些蛋糕尽可能多地分成若干相同的组做为给其他小伙伴的礼品。相同指的是每一组蛋糕都包含相同数量的不同种类的蛋糕，且最终不能有蛋糕剩下。（注意不能把一个蛋糕分成多份）

例如：小A有3种蛋糕，1号蛋糕有4个，2号蛋糕有6个，3号蛋糕有18个。那么小A最多就只能分出2组相同的礼品，每组礼品包含2个1号蛋糕，3个2号蛋糕，9个3号蛋糕。

但小A现在希望能分出更多组礼品来，又同时要保证每组蛋糕相同。

于是他决定做这样一件事情，小A将挑出若干种类的蛋糕，让这些特定种类的蛋糕不再做为礼品，也相当于把它们去掉。

比如：小A有3种蛋糕，1号蛋糕有4个，2号蛋糕有6个，3号蛋糕有18个。小A如果选择让1号蛋糕不再为礼品，那么他就最多可以分出3组相同的蛋糕，每组包含2个2号蛋糕，和6个3号蛋糕。

现在小A想要知道，他最少要选出几种蛋糕让它们不再是礼品，才能使得比刚开始分出的组数更多。你需要输出这个最小值。

假如小A无论如何都没有办法做到分出更多组相同蛋糕的话，输出不去掉任何蛋糕的情况下我们最多能够分出多少组相同的蛋糕。

注意：?一、刚开始能够分出的组数有可能为0。 二、让所有种类的蛋糕都不作为礼物的话，最后相当于只能分0组。

【输入】

第一行，一个正整数n表示有n种蛋糕。

接下来一行一共n个用空格分隔的正整数ai，表示第i种蛋糕的数量。

【输出】

一行，如果小A无法让分出的组数变多，输出一个正整数，表示最多能够分出多少组相同的蛋糕。

否则的话，输出一个正整数，表示最少要选出几种蛋糕不再作为礼物。

【输入样例】

3
2 2 2

【输出样例】

2

【代码详解】

#include <bits/stdc++.h>
using namespace std;
int n, a, c[2000005];
int gcd(int a, int b)
{
    int r = a % b;
    while (r!=0) {
        a = b; 
        b = r;
        r = a % b;
    }
    return b;

}
int main()
{
    cin >> n;
    int g = 0;  //计算多个数的公因数，初始g要设置为0
    for (int i=1; i<=n; i++) {
        cin >> a;
        g = gcd(g, a);
        for (int j=1; j*j<=a; j++) {
            if (a%j==0) {
                c[j]++;
                if (j*j!=a) c[a/j]++;
            }
        }
    }
    int ans = 0;
    for (int i=g+1; i<=2000000; i++) {
        ans = max(ans, c[i]);  // c[i]:表示以i为因数的个数
    }
    // cout << "ans "  << ans << endl;
    if (ans==0) cout << g << endl;
    else cout << n-ans << endl;
    // cout << g << endl;
    return 0;
}

【运行结果】

3
2 2 2
2