rt.

WA on #12

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a[4000005],l[4000005],r[4000005];
int cost(int l,int r){
	int g=0;
	for(int i=l;i<=r;i++) g=__gcd(g,a[i]);
	return g;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,k,mn=1e9;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mn=min(mn,a[i]);
	}
	int qwq=0;
	for(int i=1;i<=n;i++){
		if(a[i]!=mn) qwq=1;
	}
	if(!qwq){
		cout<<"0\n";
		return 0;
	}
	for(int i=1;i<=n;i++){
		if(a[i]%mn){
			cout<<n+k<<"\n";
			return 0;
		}
	}
	int tot=0;
	for(int i=1;i<=n;i++){
		if(a[i]!=mn){
			l[++tot]=i;
			r[tot]=n;
			for(int j=i;j<=n;j++){
				if(a[j]==mn){
					r[tot]=j-1;
					break;
				}
			}
			i=r[tot];
		}
	}
	int L=l[1],lst=cost(l[1],r[1]),ans=0;
	for(int i=2;i<=tot;i++){
		int c=cost(l[i],r[i]);
		int w=l[i]-r[i-1]-1;
		if(c!=mn) w--;
		if(lst!=mn) w--;
		if(w<k){
			lst=cost(l[i-1],r[i]);
		}else{
			ans+=r[i-1]-L+1+k;
			if(cost(L,r[i-1])!=mn) ans++;
			L=l[i];
		}
	}
	ans+=r[tot]-L+1+k;
	if(cost(L,r[tot])!=mn) ans++;
	cout<<ans<<"\n";
	return 0;
}