rt，自认为码风良好（

#include<bits/stdc++.h>
#define int long long
#define ioc ios::sync_with_stdio(0)
using namespace std;
const int MAXN=4e6+5;
int n,k;
int a[MAXN],l[MAXN],r[MAXN],pos[MAXN],len[MAXN],isg[MAXN],cnt=1,cnt1,g;
signed main(){
    ioc;cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    	if(i==1) g=a[i];
		else g=__gcd(g,a[i]);
	}
	for(int i=1;i<=n;i++){
		if(a[i]==g) pos[++cnt1]=i;
	}
	if(pos[1]!=1){
		l[1]=1;r[1]=pos[1]-1;len[1]=r[1]-l[1]+1+k;
	}
	for(int i=1;i<cnt1;i++){
		while(pos[i]+1==pos[i+1]) i++;
		if(i==cnt1) break;
		l[++cnt]=pos[i]+1;
		r[cnt]=pos[i+1]-1;
		len[cnt]=r[cnt]-l[cnt]+1+k;
	}
	if(pos[cnt1]<n){
		l[++cnt]=pos[cnt1]+1;
		r[cnt]=n;
		len[cnt]=r[cnt]-l[cnt]+1+k;
	}
	for(int i=1;i<=cnt;i++){
		isg[i]=1;
		int pp=a[l[i]];
		for(int j=l[i]+1;j<=r[i];j++){
			pp=__gcd(pp,a[j]);
		}
		if(pp==g) isg[i]=0;//isg表示是否需要 a[l-1] 或 a[r+1] 来提供全局gcd.
		//cout<<l[i]<<" "<<r[i]<<" "<<len[i]<<" "<<isg[i]<<"\n";
	}
	for(int i=1;i<cnt;i++){
		if(r[i+1]-l[i]+1+k<len[i]+len[i+1]+isg[i]+isg[i+1]){
			len[i]=0;l[i+1]=l[i];
			len[i+1]=r[i+1]-l[i]+1+k;//尝试合并区间
		}
	}
	int ans=0;
	for(int i=1;i<=cnt;i++){
		ans+=len[i];
	}
	cout<<ans;
}