网站首页
编程语言
数据库
系统相关
其他分享
编程问答
CF2013E
2024-09-22
CF2013E prefix gcd
给n个数,随意排序,所有前缀的gcd的和的最小值。只想到gcd变化是log次的,所以枚举每个作为开头,然后找让gcd变小的接上。可是这样是\(O(n^2)\).注意,最小的数要放最前面。假设\(x,a_1,a_2....\)和\(a_1,a_2,x...\).(x是最小的)我们有\(x+gcd(a_1,x)\leqa_1\),因为gcd的求法是\(a_