Description

solution

正解：尺取法.

很容易想到尺取法，维护左右指针，\(a[i]\%a[j]==K\)，当且仅当 \(a[j]>K\) 并且 \(a[i]-K\) 的约数中含有 \(a[j]\)，或者 \(a[i]==K\) 时存在矛盾，所以这就是移动左指针的条件，答案每一次加上合法区间长度即可

#include <algorithm>

#include <iostream>

#include <cstdlib>

#include <cstring>

#include <cstdio>

#include <cmath>

#define RG register

#define il inline

#define iter iterator

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

typedef long long ll;

const int N=100005;

int n,K,a[N],t[N],vis[N];

inline void upd(int x,int ad){

	int lim=sqrt(x);

  	for(RG int i=1;i<=lim;i++){

		if(x%i==0){

			t[i]+=ad;

			if(i*i!=x)t[x/i]+=ad;

		}

	}

}

void work()

{

	scanf("%d%d",&n,&K);

	for(int i=1;i<=n;i++)scanf("%d",&a[i]);

	int l=1;ll ans=0;

	for(int i=1;i<=n;i++){

		while(l<i && a[i]>K && (t[a[i]] || vis[K]))

			upd(a[l]-K,-1),vis[a[l]]--,l++;

		upd(a[i]-K,1);

		vis[a[i]]++;

		ans+=i-l+1;

	}

	cout<<ans<<endl;

}

int main()

{

	work();

	return 0;

}