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) \leq a_1\)， 因为gcd的求法是\(a_1 - k*x\) (qaq脑残想不到）

 void work(){
  int n;
  cin>>n;
  int g = 0;
  for(int i = 1;i <= n; i++){
    cin>>a[i];
    g = gcd(a[i], g);
  }
  for(int i = 1;i <= n; i++)a[i] /= g;
  sort(a + 1, a + 1 + n);
  LL sum = 0;
  int cur = 0;
  for(int i = 1;i <= n; i++){
    int min_a = 1e9;
    int pos = -1;
    for(int j = i;j <= n; j++){
      if(gcd(cur, a[j]) < min_a){
        min_a = gcd(cur, a[j]);
        pos = j;
      }
    }
    assert(pos != -1);
    cur = min_a;
    if(cur == 1){
      sum += n - i + 1;
      break;
    }
    sum += min_a;
    swap(a[i], a[pos]);
  }
  cout<<sum * g<<endl;
}