写的贪心。
代码有解释qwq

//Author: Velvet on Luogu(uid=443675)
#include <bits/stdc++.h>
#define int long long
#define mkpr make_pair
#define fi first
#define se second
#define F(i,a,b) for(int i=(a);i<=(b);i++)
#define dF(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
using namespace __gnu_cxx;
typedef pair<int,int> Pair;
const int N=10000005;
int n,m,G,ans,a[N];
vector<int> pg;
struct S{int l,r,Ans;};
vector<S> v;
signed main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>m;
	F(i,1,n) cin>>a[i];
	G=a[1];F(i,1,n) G=__gcd(G,a[i]);
	F(i,1,n) if(a[i]==G) pg.push_back(i);//处理出已经是答案的位置
	//下面按照pg分段 比如 2 2 2 1 2 2 2 1 2 2  
	//就是分成 (222)1(222)1(22);
	if(pg[0]>=2) v.push_back({1,pg[0]-1,pg[0]-1+m});
	F(i,0,pg.size()-2){
		if(pg[i+1]-pg[i]==1) continue;
		v.push_back({pg[i]+1,pg[i+1]-1,pg[i+1]-pg[i]-1+m});
	}
	if(pg.back()<n) v.push_back({pg.back()+1,n,n-pg.back()+m});
	//下面记录每一段内的gcd是不是答案，如果不是，还要加上左边（或者右边）的全局gcd的一个贡献
	F(i,0,v.size()-1){
		int g=a[v[i].l];
		F(j,v[i].l,v[i].r) g=__gcd(g,a[j]);
		if(g!=G) v[i].Ans++;
	}
	//枚举能否合并两个区间
	F(i,0,v.size()-2)
		if(v[i+1].r-v[i].l+1+m<v[i].Ans+v[i+1].Ans)
			v[i].Ans=0,v[i+1]={v[i].l,v[i+1].r,v[i+1].r-v[i].l+1+m};
	F(i,0,v.size()-1) ans+=v[i].Ans;
	cout<<ans;
    return 0;
}