大致思路： $gcd(a_i, a_{i+1}, a_{i+2}, \dots, a_{j}) = min(a_i, a_{i+1}, a_{i+2}, \dots, a_j)$ 意思就是一个序列里所有数都是最小数的倍数。

于是枚举最小数，处理得到符合此条件的已经无法拓展的若干个区间$[i,j]$，那么这些点两两可以以 $min(a_i, a_{i+1}, a_{i+2}, \dots, a_j)$ 的代价互相到达。

建立线段树 $t[i]$,其中 $t[i].v$ 代表使$t[i].l$ 到 $t[i].r$ 中所有点联通的价值。

于是将每个区间按$min(a_i, a_{i+1}, a_{i+2}, \dots, a_j)$ 从大到小排序，舍弃大于$p$的，剩下使用线段树依次进行区间赋值，那么最小生成树的边权和即为 $t[i].v$。

校内模拟赛的题，测了三个样例以及自己设计的数据均OK，但测的时候前两个$Subtask$都有一两个点错（每个$Subtask$大约10个点）

感觉自己写对了，应该是这种做法假掉了，但找不出假在哪里（是我太弱）

#include<bits/stdc++.h>
using namespace std;
int n,q,a[1000001],cnt=0,mid;

struct no
{
   int x,y,p;
   friend bool operator<(no c,no d)
   {
   	return c.p>d.p;
   }
}t[2000011];
struct noo
{
   long long l,r,v,la;
}tr[4000001];
void inline build(int l,int r,int k)
{
   if(l==r)
   {
   tr[k].l=l,tr[k].r=r,tr[k].v=q;
   return ;
   }
   mid=l+r>>1;
   build(l,mid,k<<1);
   mid=l+r>>1;
   build(mid+1,r,(k<<1)+1);
   tr[k].l=l,tr[k].r=r,tr[k].v=tr[k<<1].v+tr[(k<<1)+1].v;
}
void inline xg(int l,int r,int x,int k)
{
   if(l<=tr[k].l&&r>=tr[k].r)
   {
   	tr[k].la=x;
   	tr[k].v=(tr[k].r-tr[k].l+1)*x;
   	return ;
   }
   if(tr[k].l!=tr[k].r&&tr[k].la!=0)
   {
   tr[k<<1].la=tr[(k<<1)+1].la=tr[k].la;
   tr[k<<1].v=(tr[k<<1].r-tr[k<<1].l+1)*x;
   tr[(k<<1)+1].v=(tr[(k<<1)+1].r-tr[(k<<1)+1].l+1)*x;
   tr[k].la=0;
   }
   if(l<=tr[k<<1].r)xg(l,r,x,k<<1);
   if(r>=tr[(k<<1)+1].l)xg(l,r,x,(k<<1)+1);
   tr[k].v=tr[k<<1].v+tr[(k<<1)+1].v;
}
int main()
{
   freopen("mst.in","r",stdin);
   freopen("mst.out","w",stdout);
   scanf("%d%d",&n,&q);
   for(int i=1;i<=n;i++)
   scanf("%d",&a[i]);
   for(int i=1,j=1;i<=n;)
   {
   while(a[j]%a[i]==0&&j<=n)
   j++;
   j--;
   if(j!=i)
   {
   cnt++;
   t[cnt].x=i,t[cnt].y=j-1,t[cnt].p=a[i];
   }
   i=j+1;
   j++;
   }
   
   for(int i=n,j=n;i>=1;)
   {
   while(a[j]%a[i]==0&&j>=1)
   j--;
   j++;
   
   if(j!=i)
   {
   ++cnt;
   t[cnt].x=j,t[cnt].y=i-1,t[cnt].p=a[i];
   }
   i=j-1;
   j--;
   }
   sort(t+1,t+cnt+1);
   build(1,n-1,1);
   //cout<<tr[3].l<<endl;
   for(int i=1;i<=cnt;i++)
   if(t[i].p<=q)
   {
       //cout<<t[i].x<<" "<<t[i].y<<" "<<t[i].p<<endl;
   	xg(t[i].x,t[i].y,t[i].p,1);
   }
   printf("%lld\n",tr[1].v);
}