#include<bits/stdc++.h>
using namespace std;
int a[4000006];
int main(){/*
	freopen("input.in","r",stdin);
	freopen("output.out","w",stdout);*/
	ios::sync_with_stdio(false);cin.tie(0);
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++)cin>>a[i];
	int gc=a[1];//所有数的最大公因数
	for(int i=2;i<=n;i++){
		gc=__gcd(gc,a[i]);
		if(gc==1)break;
	} 
	int p=1;
	while(p<=n&&a[p]==gc)p++;
	long long ans=0;
	int status=1;
    /*
    	表示状态，1为不使用这个值，2为用了但没有找到最大公因数，3为找到了判断后面。
    */
	int t=0,l,r,u;
	for(int i=p;i<=n;i++){
		if(status==1&&a[i]!=gc){
			t=a[i];
			status=2;
			l=i;
		}
		else if(status==2){
			t=__gcd(a[i],t);
			if(t==gc){
				status=3;
				u=k;
				r=i;
			}
		}
		else if(status==3){
			if(a[i]==gc){
				if(u==0){
					ans+=(r-l+1+k);
					status=1;
				}else{
					u--;
				}
			}else{
				u=k;
				r=i;
			}
		}
	}
	
	if(status>=2){
		ans+=(n-l+1+k+(status==2));
	}
	cout<<ans; 
	return 0;
}