题解 | 小红的k次方

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); // IO加速，适配大数据量
    
    int n;
    cin >> n;
    int cnt2 = 0, cnt3 = 0, cnt5 = 0; // 统计2、3、5的质因子总个数
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
        int num = v[i];
        // 分解质因子2，统计个数
        while (num % 2 == 0) {
            cnt2++;
            num /= 2;
        }
        // 分解质因子3，统计个数
        while (num % 3 == 0) {
            cnt3++;
            num /= 3;
        }
        // 分解质因子5，统计个数
        while (num % 5 == 0) {
            cnt5++;
            num /= 5;
        }
        // 其他质因子无需处理
    }
    // 答案为三个质因子个数的最小值
    int k = min({cnt2, cnt3, cnt5});
    cout << k << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")

直接模拟会溢出，采用质因数分解的方法，对30取模就把30质因数分解成2，3，5，再看看每个数组中的元素包含多少个质因数，统计整个数组所包含的质因数个数，取这三种质因数的最小值，为什么是最小值呢？因为只有取最小才能保证含有k个2，3，5这样一定可以整除掉30，假设取最大则无法凑出多的30也就会有余数除不掉了。