#include <bits/stdc++.h>

#define int long long
#define endl '\n'

#define all(x) x.begin(), x.end()
#define sz(x) (int)((x).size())

using namespace std;

void solve([[maybe_unused]] int test_case){
    int n,q;
    cin>>n>>q;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }

    const int K = 5e5+10;

    int mu[K]={0};
    for(int i=0;i<K;i++)mu[i]=-1;
    int pr[K]={0};
    for(int i=2;i<K;i++){
        if(pr[i]!=0)continue;
        for(int k = 1; k*i<K;k++){
            pr[i*k] = 1;
            mu[i*k]*=-1;
        }
        for(int k=1;k*i*i<K;k++){
            mu[k*i*i]=0;
        }
    }

    int res=0;
    int r=n;
    int arr[K]={0};
    int cnt=0;
    for(int l=n-1;l>=0;l--){
        int x = a[l];
        for(int j=2;j*j<=x;j++){
            if(x%j==0){
                // cout<<j<<" "<<mu[j]<<" <-"<<endl;
                cnt += arr[j] * mu[j];
                arr[j]++;
                if(j*j==x)continue;
                int y = x/j;
                cnt += arr[y] * mu[y];
                arr[y]++;
            }
        }
        cnt+=arr[x]*mu[x];
        // cout<<r<<" "<<cnt<<" "<<l<<endl;
        arr[x]++;
        while(cnt>=q){
            r--;
            int x = a[r];
            for(int j=2;j*j<=x;j++){
                if(x%j==0){
                    arr[j]--;
                    assert(arr[j]>=0);
                    cnt -= arr[j] * mu[j];
                    if(j*j==x)continue;
                    int y = x/j;
                    arr[y]--;
                    assert(arr[y]>=0);
                    cnt -= arr[y] * mu[y];
                }
            }
            arr[x]--;
            assert(arr[x]>=0);
            cnt-=arr[x]*mu[x];
        }
        // cout<<r<<" "<<cnt<<endl;
        res+=(n-r);
    }
    cout<<res<<endl;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int test = 1;
    // cin>>test;
    for(int _=1;_<=test;_++){
        solve(_);
    }

    return 0;
}