• 2024-09-22CF2013E 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_