题解 | 小红的k次方

# 数组所有元素的乘积x是30^k的倍数，等价于：x分解质因数后，2 的次数 ≥ k、3 的次数 ≥ k、5 的次数 ≥ k（缺一不可）。
#（因为如果 x 要被2^k×3^k×5^k整除，必须包含至少 k 个 2、k 个 3、k 个 5 作为因数）

# 题目要求 “最大的 k”，本质是：
# 统计数组所有元素的乘积中，质因数 2 的总次数（记为 cnt2）；
# 统计质因数 3 的总次数（cnt3）；
# 统计质因数 5 的总次数（cnt5）；
# 最大的 k 就是 min(cnt2, cnt3, cnt5)（因为 k 不能超过任何一个质因数的次数，否则不满足 “倍数” 条件）。
import sys
data = list(sys.stdin.read().splitlines())
n=int(data[0])
a=list(map(int,data[1].split()))
cnt2=0
cnt3=0
cnt5=0
for i in a:
    #同一个数可能2，3，5均为其因数，且不止一个
    while i%2==0:
        cnt2+=1
        i//=2
    while i%3==0:
        cnt3+=1
        i//=3
    while i%5==0:
        cnt5+=1
        i//=5
print(min(cnt2,cnt3,cnt5))