Read problems statements in Mandarin Chinese  and Russian. 
Chef sometimes suffers from insomnia. During sleepless nights, he often plays this game: He creates an array A of N integers and also decides one integer K. After that, he tries to count the number of non-empty contiguous subsequences (subsegments) of A, such that there are no bad pairs of integers in this subsegment. A pair (x, y) of integers is called bad if x is situated to the left of y in the array and x mod y = K. Finally, before going to sleep, Chef wrote down the answer on a sheet of paper. Sadly, he has forgotten it this morning and want your help regarding that.

------ Input ------ 

The first line contains two integers - N and K.
Second line contains N integers - A_{1}, A_{2} ... A_{N} - separated by spaces, denoting the array A.

------ Output ------ 

A single line containing an integer - the answer to the problem.

------ Constraints ------ 

$1 ≤ N, A_{i} ≤ 10^{5} $
$0 ≤ K ≤ 10^{5} $

------ Subtasks ------ 

$Subtask 1: N ≤ 100 (15 points) $
$Subtask 2: N ≤ 1000 (15 points) $
$Subtask 3: K = 0 (10 points) $
$Subtask 4: Original constraints (60 points) $

----- Sample Input 1 ------ 
3 2
5 3 1
----- Sample Output 1 ------ 
4

Source: codechef | Difficulty: HARD
Tags: Constructive algorithms

Range queries

Number theory

Mathematics

Ad-hoc


Solutions:
(n, k) = list(map(int, input().split()))
arr = list(map(int, input().split()))
s = 1
max_num = arr[0]
prev = -1
index_map = {}
index_map[arr[0]] = 0
for i in range(1, n):
	if arr[i] <= k:
		s += i - prev
	else:
		for j in range(max_num // arr[i] + 1):
			if arr[i] * j + k in index_map:
				prev = max(prev, index_map[arr[i] * j + k])
		s += i - prev
	index_map[arr[i]] = i
	max_num = max(max_num, arr[i])
print(s)


import math
from collections import defaultdict
d = defaultdict()
f = defaultdict()

def factor(n):
	try:
		if f[n] != []:
			A = f[n]
			return A
	except:
		A = []
		if n == 1:
			return []
		else:
			for i in range(1, int(math.ceil(pow(n, 0.5)))):
				if n % i == 0:
					A.append(i)
					A.append(n // i)
			if pow(n, 0.5) % 1 == 0:
				A.append(int(pow(n, 0.5)))
			A.remove(1)
			f[n] = A
			return A
(n, k) = [int(x) for x in input().split()]
a = []
if n > 100:
	a = [int(x) for x in input().split()]
	ee = defaultdict()
	ee[a[n - 1]] = [n - 1, n - 1]
	i = n - 2
	rr = 1
	max1 = n
	min1 = n - 1
	while i >= 0:
		if a[i] > k:
			max1 = i
			if a[i] == 1:
				g = [1]
			else:
				g = factor(a[i] - k)
				min = n
				for j in g:
					if a[i] % j == k:
						try:
							if ee[j] != []:
								x = ee[j][0]
								if x < min:
									min = x
						except:
							t = 0
				ee[a[i]] = [i, min - 1]
		elif a[i] < k:
			ee[a[i]] = [i, n - 1]
		else:
			ee[a[i]] = [i, max1 - 1]
		if ee[a[i]][1] > min1:
			rr = rr + min1 - ee[a[i]][0] + 1
		else:
			min1 = ee[a[i]][1]
			rr = rr + min1 - ee[a[i]][0] + 1
		i = i - 1
else:
	a = [int(x) for x in input().split()]
	s = [0] * n
	i = n - 2
	s[n - 1] = n - 1
	rr = 1
	min2 = n - 1
	while i >= 0:
		j = i + 1
		while j <= min2 and a[i] % a[j] != k:
			j = j + 1
		j = j - 1
		if j < min2:
			min2 = j
		s[i] = j
		rr = rr + s[i] - i + 1
		i = i - 1
print(rr)