核心内容摘要
红桃17c，c18起草线工作正式启动：一场关于未来的精密部署
题目描述小红拿到了一个长为 n 的数组 a定义数组中所有元素的乘积为 x。
小红想知道最大的满足 x 是 30 的 k 次方的倍数形式化的x \mod 30^k 0的 k 是多少题目链接小红的k次方_牛客题霸_牛客网输入格式第一行输入一个整数 n (1≦n≦2×10^
第二行输入 n 个整数 ai (1≦ai≦10^
输出格式输出一个整数代表最大的 k示例输入430 15 2 7输出2问题分析数据规模大n 最大可达2×10^5 aᵢ 最大可达10^9乘积极大直接计算所有数的乘积会得到天文数字远超任何数据类型的范围需要高效算法必须在 O(n) 或 O(n log n) 时间内解决问题解题思路第一步数学转化30 的质因数分解302×3×5302×3×530 的 k 次方30^k(2×3×
^k2^k×3^k×5^k第二步整除条件分析设数组所有元素的乘积为 x要使 x 能被 30^k 整除即xmod 30^k0这意味着x 必须包含至少 k 个因子 2x 必须包含至少 k 个因子 3x 必须包含至少 k 个因子 5第三步得出关键结论设数组所有数中因子 2 的总个数为 cnt_2因子 3 的总个数为 cnt_3因子 5 的总个数为 cnt_5那么最大的 k 满足k≤cnt2 , k≤cnt3 , k≤cnt5因此max k min(cnt2,cnt3,cnt
第四步算法设计基于以上分析我们不需要计算巨大的乘积 x只需遍历数组中的每个数统计每个数中因子
2、
5 的个数累加得到总个数取三个总个数的最小值代码实现pythonnint(input()) arrlist(map(int,input().split())) a,b,c0,0,0 for num in arr: while num%20: a1 num//2 while num%30: b1 num//3 while num%50: c1 num//5 kmin(a,b,c) print(k)复杂度分析时间复杂度每个数需要被
2、
5整除若干次对于每个数循环次数最多为 log2 ai log3 ai log5 ai总时间复杂度O(n × log(max(a_i)))对于 n (1≦n≦2×10^
完全可行空间复杂度只需常数空间存储计数O(
错误反思错误1直接计算乘积问题乘积 x 可能达到(10⁹)^{2×10⁵} 10^{9 × 2×10⁵} 10^{
8×10⁶}远超任何数据类型范围。
错误2二分查找法虽然理论上可以用二分查找 k但需要计算 30^k 和判断整除关系同样面临大数问题且效率不如直接统计。