AtCoder Regular Contest 068 - Snuke Line

Snuke has decided to play a game, where the player runs a railway company.
There are M+1 stations on Snuke Line, numbered 0 through M.
A train on Snuke Line stops at station 0 and every d-th station thereafter, where d is a predetermined constant for each train.
For example, if d = 3, the train stops at station 0, 3, 6, 9, and so forth.
There are N kinds of souvenirs sold in areas around Snuke Line. The i-th kind of souvenirs can be purchased when the train stops at one of the following stations: stations l_i, l_i+1, l_i+2, ..., r_i.
There are M values of d, the interval between two stops, for trains on Snuke Line: 1, 2, 3, ..., M.
For each of these M values, find the number of the kinds of souvenirs that can be purchased if one takes a train with that value of d at station 0.
Here, assume that it is not allowed to change trains.

-----Constraints-----
 - 1 ≦ N ≦ 3 × 10^{5}
 - 1 ≦ M ≦ 10^{5}
 - 1 ≦ l_i ≦ r_i ≦ M

-----Input-----
The input is given from Standard Input in the following format:
N M
l_1 r_1
:
l_{N} r_{N}

-----Output-----
Print the answer in M lines. The i-th line should contain the maximum number of the kinds of souvenirs that can be purchased if one takes a train stopping every i-th station.

-----Sample Input-----
3 3
1 2
2 3
3 3

-----Sample Output-----
3
2
2

 - If one takes a train stopping every station, three kinds of souvenirs can be purchased: kind 1, 2 and 3.
 - If one takes a train stopping every second station, two kinds of souvenirs can be purchased: kind 1 and 2.
 - If one takes a train stopping every third station, two kinds of souvenirs can be purchased: kind 2 and 3.

Source: atcoder | Difficulty: HARD


Solutions:
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

class BitSum:

	def __init__(self, n):
		self.n = n + 3
		self.table = [0] * (self.n + 1)

	def add(self, i, x):
		i += 1
		while i <= self.n:
			self.table[i] += x
			i += i & -i

	def sum(self, i):
		i += 1
		res = 0
		while i > 0:
			res += self.table[i]
			i -= i & -i
		return res

def main():
	(n, m) = MI()
	dlr = []
	for _ in range(n):
		(l, r) = MI()
		dlr.append((r - l + 1, l, r + 1))
	dlr.sort()
	bit = BitSum(m + 1)
	i = 0
	for k in range(1, m + 1):
		while i < n and dlr[i][0] <= k:
			(d, l, r) = dlr[i]
			bit.add(l, 1)
			bit.add(r, -1)
			i += 1
		print(n - i + sum((bit.sum(a) for a in range(k, m + 1, k))))
main()


import sys
input = sys.stdin.readline
from collections import defaultdict
(N, M) = map(int, input().split())
d_to_LR = defaultdict(list)
for _ in range(N):
	(L, R) = map(int, input().split())
	d_to_LR[R - L + 1].append((L, R))

def BIT_update(tree, x, value):
	while x <= M:
		tree[x] += value
		x += x & -x

def BIT_sum(tree, x):
	s = 0
	while x:
		s += tree[x]
		x -= x & -x
	return s
tree = [0] * (M + 1)
long = N
answer = [0] * (M + 1)
for m in range(1, M + 1):
	for (L, R) in d_to_LR[m]:
		BIT_update(tree, L, 1)
		BIT_update(tree, R + 1, -1)
		long -= 1
	answer[m] = sum((BIT_sum(tree, x) for x in range(m, M + 1, m))) + long
print('\n'.join(map(str, answer[1:])))


import sys
from operator import itemgetter
mod = 10 ** 9 + 7
inf = 1 << 30

def solve():
	(N, M) = map(int, sys.stdin.readline().split())
	sects = []
	for i in range(N):
		(li, ri) = map(int, sys.stdin.readline().split())
		sects.append((li - 1, ri, ri - li + 1))
	sects.sort(key=itemgetter(2))
	print(N)
	left = 0
	ft = FenwickTree([0] * (M + 1))
	for d in range(2, M + 1):
		for j in range(left, N):
			if sects[j][2] >= d:
				left = j
				break
			else:
				ft.add(sects[j][0], 1)
				ft.add(sects[j][1], -1)
		else:
			left = N
		ans = N - left + sum((ft.get_sum(j) for j in range(d, M + 1, d)))
		print(ans)

class FenwickTree:

	def __init__(self, a):
		self.n = len(a)
		self.data = [0] + a[:]
		for i in range(1, self.n + 1):
			if i + (i & -i) <= self.n:
				self.data[i + (i & -i)] += self.data[i]

	def add(self, i, x):
		i += 1
		while i <= self.n:
			self.data[i] += x
			i += i & -i

	def get_sum(self, r):
		res = 0
		while r > 0:
			res += self.data[r]
			r -= r & -r
		return res

def __starting_point():
	solve()
__starting_point()


import sys
input = sys.stdin.readline

def solve():

	def makeBIT(numEle):
		numPow2 = 2 ** (numEle - 1).bit_length()
		data = [0] * (numPow2 + 1)
		return (data, numPow2)

	def addValue(iA, A):
		iB = iA + 1
		while iB > 0:
			data[iB] += A
			iB -= iB & -iB

	def getValue(iA):
		iB = iA + 1
		ans = 0
		while iB <= numPow2:
			ans += data[iB]
			iB += iB & -iB
		return ans

	def addRangeValue(iFr, iTo, A):
		addValue(iTo, A)
		if iFr > 0:
			addValue(iFr - 1, -A)
	(N, M) = list(map(int, input().split()))
	LRss = [[] for _ in range(M + 1)]
	for _ in range(N):
		(L, R) = list(map(int, input().split()))
		LRss[R - L + 1].append((L, R))
	(data, numPow2) = makeBIT(M + 1)
	anss = []
	numOK = N
	for d in range(1, M + 1):
		ans = numOK
		for i in range(d, M + 1, d):
			ans += getValue(i)
		anss.append(ans)
		numOK -= len(LRss[d])
		for (L, R) in LRss[d]:
			addRangeValue(L, R, 1)
	print('\n'.join(map(str, anss)))
solve()


from bisect import bisect
from operator import itemgetter
import sys
input = sys.stdin.readline

def inpl():
	return list(map(int, input().split()))

class BIT:

	def __init__(self, N):
		self.size = 2 ** (int.bit_length(N) + 1)
		self.tree = [0] * (self.size + 1)

	def sum(self, i):
		res = 0
		while i:
			res += self.tree[i]
			i -= i & -i
		return res

	def add(self, i, x):
		if i == 0:
			return
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

class RABIT:

	def __init__(self, N):
		self.bit0 = BIT(N)
		self.bit1 = BIT(N)

	def sum(self, i):
		return i * self.bit1.sum(i) + self.bit0.sum(i)

	def add_range(self, l, r, x):
		self.bit0.add(l, -x * (l - 1))
		self.bit1.add(l, x)
		self.bit0.add(r + 1, x * r)
		self.bit1.add(r + 1, -x)

	def get_range(self, l, r):
		return self.sum(r) - self.sum(l - 1)
(N, M) = inpl()
(R, L, S) = ([], [], [])
Q = []
for _ in range(N):
	(l, r) = inpl()
	Q.append((l, r, r - l + 1))
Q = sorted(Q, key=itemgetter(2), reverse=True)
rabit = RABIT(M + 1)
Lmin = M
Rmax = 0
for i in range(1, M + 1):
	while Q and Q[-1][2] < i:
		(l, r, _) = Q.pop()
		rabit.add_range(l, r, 1)
		Lmin = min(Lmin, l)
		Rmax = max(Rmax, r)
	ans = len(Q)
	for j in range(-(-Lmin // i) * i, Rmax + 1, i):
		ans += rabit.get_range(j, j)
	print(ans)


import sys

def input():
	return sys.stdin.readline()[:-1]
(N, M) = map(int, input().split())
L = []
for i in range(N):
	(l, r) = map(int, input().split())
	L.append((r - l + 1, l, r + 1))
L.sort()

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		if not 0 <= i <= self.size:
			raise ValueError('error!')
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		if not 0 <= i < self.size:
			raise ValueError('error!')
		i += 1
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

class BitImos:

	def __init__(self, n):
		self.bit = Bit(n + 1)

	def add(self, s, t, x):
		self.bit.add(s, x)
		self.bit.add(t, -x)

	def get(self, i):
		return self[i]

	def __getitem__(self, key):
		return self.bit.sum(key + 1)
imos = BitImos(M + 1)
il = 0
a = N
A = [0] * M
for i in range(1, M + 1):
	while il < N:
		(ra, l, r) = L[il]
		if i < ra:
			break
		il += 1
		a -= 1
		imos.add(l, r, 1)
	ans = 0
	for j in range(i, M + 1, i):
		ans += imos[j]
	A[i - 1] = ans + a
print(*A, sep='\n')


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
NN = (M + 10).bit_length()
BIT = [0] * (2 ** NN + 1)

def addrange(l0, r0, x=1):
	(l, r) = (l0, r0)
	while l <= 2 ** NN:
		BIT[l] += x
		l += l & -l
	while r <= 2 ** NN:
		BIT[r] -= x
		r += r & -r

def getvalue(r):
	a = 0
	while r != 0:
		a += BIT[r]
		r -= r & -r
	return a
X = []
for _ in range(N):
	(l, r) = map(int, input().split())
	X.append((l, r + 1))
X = sorted(X, key=lambda x: -(x[1] - x[0]))
for d in range(1, M + 1):
	while X and X[-1][1] - X[-1][0] < d:
		(l, r) = X.pop()
		addrange(l, r)
	ans = len(X)
	for i in range(d, M + 1, d):
		ans += getvalue(i)
	print(ans)


import sys
input = sys.stdin.readline

def bit_add(i, x):
	while i <= M:
		tree[i] += x
		i += i & -i

def bit_sum(i):
	s = 0
	while i > 0:
		s += tree[i]
		i -= i & -i
	return s
(N, M) = map(int, input().split())
data = []
for i in range(N):
	(l, r) = map(int, input().split())
	data.append([r - l, l, r])
data.sort()
k = 0
tree = [0] * (M + 1)
for d in range(1, M + 1):
	while k < N and data[k][0] < d:
		bit_add(data[k][1], 1)
		bit_add(data[k][2] + 1, -1)
		k += 1
	ans = 0
	for j in range(1, M // d + 1):
		ans += bit_sum(d * j)
	print(ans + N - k)


def bitadd(a, w, bit):
	x = a
	while x <= len(bit) - 1:
		bit[x] += w
		x += x & -1 * x

def bitsum(x, bit):
	ret = 0
	while x:
		ret += bit[x]
		x -= x & -1 * x
	return ret

def bitaddR(l, r, w, bit1, bit2):
	bitadd(l, -1 * w * l, bit1)
	bitadd(r, w * r, bit1)
	bitadd(l, w, bit2)
	bitadd(r, -1 * w, bit2)

def bitsumR(r, bit1, bit2):
	return bitsum(r, bit1) + r * bitsum(r, bit2)
(N, M) = list(map(int, input().split()))
BIT = [0] * (M + 1)
dic = {}
for i in range(N):
	(l, r) = list(map(int, input().split()))
	if r - l + 1 not in dic:
		dic[r - l + 1] = []
	dic[r - l + 1].append([l, r])
ind = 0
ns = N
ans = []
for d in range(M):
	d += 1
	if d in dic:
		for (L, R) in dic[d]:
			bitadd(L, 1, BIT)
			bitadd(R + 1, -1, BIT)
			ns -= 1
	nm = 0
	for i in range(d, M + 1, d):
		nm += bitsum(i, BIT)
	ans.append(nm + ns)
print('\n'.join(map(str, ans)))


from operator import itemgetter
import sys
input = sys.stdin.readline

class BIT:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def _add(self, i, val):
		while i > 0:
			self.bit[i] += val
			i -= i & -i

	def get_val(self, i):
		i = i + 1
		s = 0
		while i <= self.n:
			s += self.bit[i]
			i += i & -i
		return s

	def add(self, l, r, val):
		self._add(r, val)
		self._add(l, -val)
(n, m) = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
for i in range(n):
	info[i] = (info[i][0], info[i][1], info[i][1] - info[i][0] + 1)
info = sorted(info, key=itemgetter(2))
bit = BIT(m + 1)
l_info = 0
ans = n
res = [0] * m
for d in range(1, m + 1):
	while True:
		if l_info < n and info[l_info][2] < d:
			(l, r, _) = info[l_info]
			bit.add(l, r + 1, 1)
			l_info += 1
			ans -= 1
		else:
			break
	cnt = ans
	for i in range(0, m + 1, d):
		cnt += bit.get_val(i)
	res[d - 1] = cnt
print('\n'.join(map(str, res)), end='\n')


import sys
input = sys.stdin.readline

def main():
	(n, m) = map(int, input().split())
	LR = [list(map(int, input().split())) for _ in range(n)]
	BIT = [0] * (m + 2)

	def add(i, a):
		while i <= m + 1:
			BIT[i] += a
			i += i & -i

	def bit_sum(i):
		res = 0
		while i > 0:
			res += BIT[i]
			i -= i & -i
		return res
	S = sorted([(r - l + 1, l, r) for (l, r) in LR], reverse=True)
	cnt = n
	L = []
	for i in range(1, m + 1):
		while S and S[-1][0] == i:
			(c, l, r) = S.pop()
			cnt -= 1
			add(l, 1)
			add(r + 1, -1)
		res = cnt
		for j in range(0, m + 1, i):
			res += bit_sum(j)
		L.append(res)
	print(*L, sep='\n')

def __starting_point():
	main()
__starting_point()


def main():
	(n, m) = map(int, input().split())
	lr = [tuple(map(int, input().split())) for _ in range(n)]
	BIT = [0 for _ in range(m + 1)]

	def bit_add(a, w):
		x = a
		while x <= m:
			BIT[x] += w
			x += x & -x

	def bit_sum(a):
		ret = 0
		x = a
		while x > 0:
			ret += BIT[x]
			x -= x & -x
		return ret
	lr = list(sorted(lr, key=lambda x: x[1] - x[0]))
	i = 1
	for d in range(1, m + 1):
		while i <= n and lr[i - 1][1] - lr[i - 1][0] + 1 == d:
			bit_add(lr[i - 1][0], 1)
			bit_add(lr[i - 1][1] + 1, -1)
			i += 1
		ans = n - i + 1
		for j in range(d, m + 1, d):
			ans += bit_sum(j)
		print(ans)
main()


class BIT(object):

	def __init__(self, size):
		self.size = size
		self.bit = [0] * (self.size + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.bit[i] += x
			i += i & -i

	def __str__(self):
		return str(self.bit)
(n, m) = map(int, input().split())
lr = [[] for i in range(m + 1)]
for i in range(n):
	(l, r) = map(int, input().split())
	lr[r - l + 1].append(l)
bit = BIT(m + 1)
t = 0
for d in range(1, m + 1):
	for l in lr[d]:
		bit.add(l, 1)
		bit.add(l + d, -1)
	t += len(lr[d])
	ans = n - t
	cur = 0
	while cur <= m:
		ans += bit.sum(cur)
		cur += d
	print(ans)


class BIT:

	def __init__(self, n):
		self.n = n
		self.data = [0] * (n + 1)
		self.el = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		self.el[i] += x
		while i <= self.n:
			self.data[i] += x
			i += i & -i

	def get(self, i, j=None):
		if j is None:
			return self.el[i]
		return self.sum(j) - self.sum(i)

class BIT_Range:

	def __init__(self, n):
		self.n = n
		self.bit0 = BIT(n + 1)
		self.bit1 = BIT(n + 1)

	def add(self, l, r, x):
		l += 1
		self.bit0.add(l, -x * (l - 1))
		self.bit0.add(r + 1, x * r)
		self.bit1.add(l, x)
		self.bit1.add(r + 1, -x)

	def sum(self, i):
		if i == 0:
			return 0
		return self.bit0.sum(i) + self.bit1.sum(i) * i

	def get(self, i):
		return self.sum(i + 1) - self.sum(i)

	def get_range(self, i, j):
		return self.sum(j) - self.sum(i)

def main1(n, m, lr):
	lary = [[] for _ in range(m + 1)]
	for (l, r) in lr:
		lary[r - l + 1].append([l, r])
	ret = [n]
	bitr = BIT_Range(m + 1)
	cnt = 0
	for d in range(2, m + 1):
		for (l, r) in lary[d - 1]:
			cnt += 1
			bitr.add(l, r + 1, 1)
		tmp = n - cnt
		dd = d
		while dd <= m:
			tmp += bitr.get(dd)
			dd += d
		ret.append(tmp)
	return ret

def __starting_point():
	(n, m) = map(int, input().split())
	lr = [list(map(int, input().split())) for _ in range(n)]
	print(*main1(n, m, lr), sep='\n')
__starting_point()


class BITbisect:

	def __init__(self, max):
		self.max = max
		self.data = [0] * (self.max + 1)

	def query_sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.max:
			self.data[i] += x
			i += i & -i

	def insert(self, x):
		self.add(x, 1)

	def delete(self, x):
		self.add(x, -1)

	def count(self, x):
		return self.query_sum(x) - self.query_sum(x - 1)

	def length(self):
		return self.query_sum(self.max)

	def search(self, c):
		c += 1
		s = 0
		ind = 0
		l = self.max.bit_length()
		for i in reversed(range(l)):
			if ind + (1 << i) <= self.max:
				if s + self.data[ind + (1 << i)] < c:
					s += self.data[ind + (1 << i)]
					ind += 1 << i
		if ind == self.max:
			return False
		return ind + 1

	def bisect_right(self, x):
		return self.query_sum(x)

	def bisect_left(self, x):
		if x == 1:
			return 0
		return self.query_sum(x - 1)

	def display(self):
		print('inside BIT:', end=' ')
		for x in range(1, self.max + 1):
			if self.count(x):
				c = self.count(x)
				for _ in range(c):
					print(x, end=' ')
		print()
import sys
input = sys.stdin.readline
base = 10 ** 9
(N, M) = map(int, input().split())
Pairs = [[] for _ in range(M + 1)]
for _ in range(N):
	(a, b) = map(int, input().split())
	Pairs[b - a + 1].append(a * base + b)
ansbit = BITbisect(M + 1)
usingbit = BITbisect(M + 1)
for (length, inPairs) in enumerate(Pairs):
	if length == 0:
		continue
	ansbit.add(1, len(inPairs))
	ansbit.add(length + 1, -len(inPairs))
	rem = M // length
	c = 0
	for r in range(1, rem + 1):
		c += usingbit.query_sum(r * length)
	ansbit.add(length, c)
	ansbit.add(length + 1, -c)
	for p in inPairs:
		l = p // base
		r = p % base
		usingbit.add(l, 1)
		usingbit.add(r + 1, -1)
for n in range(1, M + 1):
	print(ansbit.query_sum(n))


from collections import defaultdict
(N, M) = map(int, input().split())
section = [list(map(int, input().split())) for i in range(N)]
D = defaultdict(list)
for sec in section:
	D[sec[1] - sec[0] + 1].append(sec)

class BinaryIndexedTree:

	def __init__(self, n):
		self.size = n
		self.bit = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.bit[i] += x
			i += i & -i

	def reset(self):
		self.bit = [0] * (self.size + 1)
BIT = BinaryIndexedTree(M)
certainly = 0
for d in range(1, M + 1):
	for (l, r) in D[d - 1]:
		certainly += 1
		BIT.add(l, 1)
		BIT.add(r + 1, -1)
	ans = N - certainly
	for i in range(d, M + 1, d):
		ans += BIT.sum(i)
	print(ans)


import math
import itertools
import heapq
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect, bisect_left, bisect_right
from collections import defaultdict, deque

def LM(t, r):
	return list(map(t, r))

def R():
	return stdin.readline()

def RS():
	return R().split()

def I():
	return int(R())

def F():
	return float(R())

def LI():
	return LM(int, RS())

def LF():
	return LM(float, RS())

def ONE_SL():
	return list(input())

def ONE_IL():
	return LM(int, ONE_SL())

def ALL_I():
	return map(int, stdin)

def ALL_IL():
	return LM(int, stdin)

def ap(f):
	return f.append

def pll(li):
	print('\n'.join(LM(str, li)))

def pljoin(li, s):
	print(s.join(li))

class BIT(object):

	def __init__(self, l):
		self.size = l
		self.bit = [0] * (self.size + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i < self.size:
			self.bit[i] += x
			i += i & -i

	def __str__(self):
		return str(self.bit)

def main():
	(N, M) = LI()
	bit = BIT(M + 2)
	L = []
	R = []
	b = [[] for i in range(M + 1)]
	for i in range(N):
		(l, r) = LI()
		L.append(l)
		R.append(r)
		b[r - l + 1].append(i)
	gone = 0
	for d in range(1, M + 1):
		for i in b[d]:
			gone += 1
			bit.add(L[i], 1)
			bit.add(R[i] + 1, -1)
		ans = N - gone
		for m in range(d, M + 1, d):
			ans += bit.sum(m)
		print(ans)

def __starting_point():
	main()
__starting_point()


import sys
input = sys.stdin.readline

class BIT:

	def __init__(self, number):
		self.n = number
		self.list = [0] * (number + 1)

	def add(self, i, x):
		while i <= self.n:
			self.list[i] += x
			i += i & -i

	def search(self, i):
		s = 0
		while i > 0:
			s += self.list[i]
			i -= i & -i
		return s

	def suma(self, i, j):
		return self.search(j) - self.search(i - 1)
(N, M) = list(map(int, input().split()))
L = [[] for i in range(M + 1)]
bit = BIT(M + 1)
for i in range(N):
	(l, r) = list(map(int, input().split()))
	L[r - l + 1].append((l, r))
ans = N
for i in range(1, M + 1):
	num = 0
	for (l, r) in L[i]:
		ans -= 1
		bit.add(l, 1)
		bit.add(r + 1, -1)
	num += ans
	for j in range(i, M + 1, i):
		num += bit.search(j)
	print(num)


class Bit:

	def __init__(self, n):
		self.n = n
		self.tree = [0] * (n + 1)
		self.depth = n.bit_length() - 1

	def sum(self, i):
		s = 0
		i -= 1
		while i >= 0:
			s += self.tree[i]
			i = (i & i + 1) - 1
		return s

	def build(self, array):
		for (i, a) in enumerate(array):
			self.add(i, a)

	def add(self, i, x):
		while i < self.n:
			self.tree[i] += x
			i |= i + 1

	def get(self, i, j):
		if i == 0:
			return self.sum(j)
		return self.sum(j) - self.sum(i)

	def lower_bound(self, x, equal=False):
		sum_ = 0
		pos = -1
		if not equal:
			for i in range(self.depth, -1, -1):
				k = pos + (1 << i)
				if k < self.n and sum_ + self.tree[k] < x:
					sum_ += self.tree[k]
					pos += 1 << i
		if equal:
			for i in range(self.depth, -1, -1):
				k = pos + (1 << i)
				if k < self.n and sum_ + self.tree[k] <= x:
					sum_ += self.tree[k]
					pos += 1 << i
		return (pos, sum_)

	def __getitem__(self, i):
		return self.get(i, i + 1)

	def __iter__(self):
		for i in range(self.n):
			yield self.get(i, i + 1)

	def __str__(self):
		text1 = ' '.join(['element:            '] + list(map(str, self)))
		text2 = ' '.join(['cumsum(1-indexed):  '] + list((str(self.sum(i)) for i in range(1, self.n + 1))))
		return '\n'.join((text1, text2))

class BitImos:

	def __init__(self, n):
		self.n = n
		self.p = Bit(self.n + 1)
		self.q = Bit(self.n + 1)

	def add(self, s, t, x):
		t += 1
		self.p.add(s, -x * s)
		self.p.add(t, x * t)
		self.q.add(s, x)
		self.q.add(t, -x)

	def sum(self, s, t):
		return self.p.sum(t) + self.q.sum(t) * t - self.p.sum(s) - self.q.sum(s) * s

	def __getitem__(self, s):
		return self.q.sum(s + 1)

	def __iter__(self):
		for t in range(self.n):
			yield self.q.sum(t + 1)

	def __str__(self):
		text1 = ' '.join(['element: '] + list(map(str, self)))
		return text1
import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
data = [[] for _ in range(M + 1)]
for _ in range(N):
	(l, r) = map(int, input().split())
	data[r - l + 1].append((l, r))
B = BitImos(M + 1)
res = [0] * M
cnt = N
for d in range(1, M + 1):
	for (l, r) in data[d]:
		B.add(l, r, 1)
		cnt -= 1
	res[d - 1] += cnt
	for i in range(0, M + 1, d):
		res[d - 1] += B[i]
print(*res, sep='\n')


import sys
input = sys.stdin.readline

def main():
	(n, m) = map(int, input().split())
	S = [[] for _ in range(m + 1)]
	for _ in range(n):
		(l, r) = map(int, input().split())
		S[r - l + 1].append((l, r))
	BIT = [0] * (m + 2)

	def add(i, a):
		while i <= m + 1:
			BIT[i] += a
			i += i & -i

	def bit_sum(i):
		res = 0
		while i > 0:
			res += BIT[i]
			i -= i & -i
		return res
	cnt = n
	for i in range(1, m + 1):
		for (l, r) in S[i]:
			cnt -= 1
			add(l, 1)
			add(r + 1, -1)
		res = cnt
		for j in range(0, m + 1, i):
			res += bit_sum(j)
		print(res)

def __starting_point():
	main()
__starting_point()


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 15
mod = 10 ** 9 + 7

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

class BIT:

	def __init__(self, n):
		i = 1
		while 2 ** i <= n:
			i += 1
		self.H = i
		self.N = 2 ** i
		self.A = [0] * self.N

	def find(self, i):
		r = 0
		while i:
			r += self.A[i]
			i -= i & i - 1 ^ i
		return r

	def update(self, i, x):
		while i < self.N:
			self.A[i] += x
			i += i & i - 1 ^ i

	def query(self, a, b):
		return self.find(b - 1) - self.find(a - 1)

def main():
	(n, m) = LI()
	d = collections.defaultdict(list)
	for _ in range(n):
		(l, r) = LI()
		d[r - l + 1].append((l, r))
	r = [n]
	bit = BIT(m + 3)
	c = n
	for i in range(2, m + 1):
		for (a, b) in d[i - 1]:
			c -= 1
			bit.update(a, 1)
			bit.update(b + 1, -1)
		t = c
		for j in range(i, m + 1, i):
			t += bit.find(j)
		r.append(t)
	return '\n'.join(map(str, r))
print(main())


from collections import defaultdict

def inpl():
	return [int(i) for i in input().split()]

class BIT:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sumi(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
(N, M) = inpl()
H = defaultdict(lambda : [])
for _ in range(N):
	(l, r) = inpl()
	H[r - l + 1].append(l)
Q = BIT(M + 1)
ctr = N
for i in range(1, M + 1):
	ctr -= len(H[i])
	for j in H[i]:
		Q.add(j, 1)
		Q.add(j + i, -1)
	ans = 0
	for k in range(i, M + 1, i):
		ans += Q.sumi(k)
	print(ctr + ans)


class BIT:

	def __init__(self, n):
		self.BIT = [0] * (n + 1)
		self.num = n

	def query(self, idx):
		res_sum = 0
		while idx > 0:
			res_sum += self.BIT[idx]
			idx -= idx & -idx
		return res_sum

	def update(self, idx, x):
		while idx <= self.num:
			self.BIT[idx] += x
			idx += idx & -idx
		return
import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
q = {i: [] for i in range(1, M + 1)}
imos = [0 for i in range(M + 2)]
for i in range(N):
	(l, r) = map(int, input().split())
	q[l].append(r)
	imos[l] += 1
	imos[r + 1] -= 1
for i in range(1, M + 1):
	imos[i] += imos[i - 1]
res = {i: imos[i * (M // i)] for i in range(1, M + 1)}
query = {i: [] for i in range(1, M + 1)}
for i in range(1, M + 1):
	for j in range(1, M // i):
		query[i * j].append(i * j + i)
bit = BIT(M)
for i in range(1, M + 1):
	for r in q[i]:
		bit.update(r, 1)
	for r in query[i]:
		res[r - i] += bit.query(r - 1) - bit.query(i - 1)
for i in range(1, M + 1):
	print(res[i])


class lazy_segtree:

	def update(self, k):
		self.d[k] = self.op(self.d[2 * k], self.d[2 * k + 1])

	def all_apply(self, k, f):
		self.d[k] = self.mapping(f, self.d[k])
		if k < self.size:
			self.lz[k] = self.composition(f, self.lz[k])

	def push(self, k):
		self.all_apply(2 * k, self.lz[k])
		self.all_apply(2 * k + 1, self.lz[k])
		self.lz[k] = self.identity

	def __init__(self, V, OP, E, MAPPING, COMPOSITION, ID):
		self.n = len(V)
		self.log = (self.n - 1).bit_length()
		self.size = 1 << self.log
		self.d = [E for i in range(2 * self.size)]
		self.lz = [ID for i in range(self.size)]
		self.e = E
		self.op = OP
		self.mapping = MAPPING
		self.composition = COMPOSITION
		self.identity = ID
		for i in range(self.n):
			self.d[self.size + i] = V[i]
		for i in range(self.size - 1, 0, -1):
			self.update(i)

	def set(self, p, x):
		assert 0 <= p and p < self.n
		p += self.size
		for i in range(self.log, 0, -1):
			self.push(p >> i)
		self.d[p] = x
		for i in range(1, self.log + 1):
			self.update(p >> i)

	def get(self, p):
		assert 0 <= p and p < self.n
		p += self.size
		for i in range(self.log, 0, -1):
			self.push(p >> i)
		return self.d[p]

	def prod(self, l, r):
		assert 0 <= l and l <= r and (r <= self.n)
		if l == r:
			return self.e
		l += self.size
		r += self.size
		for i in range(self.log, 0, -1):
			if l >> i << i != l:
				self.push(l >> i)
			if r >> i << i != r:
				self.push(r >> i)
		(sml, smr) = (self.e, self.e)
		while l < r:
			if l & 1:
				sml = self.op(sml, self.d[l])
				l += 1
			if r & 1:
				r -= 1
				smr = self.op(self.d[r], smr)
			l >>= 1
			r >>= 1
		return self.op(sml, smr)

	def all_prod(self):
		return self.d[1]

	def apply_point(self, p, f):
		assert 0 <= p and p < self.n
		p += self.size
		for i in range(self.log, 0, -1):
			self.push(p >> i)
		self.d[p] = self.mapping(f, self.d[p])
		for i in range(1, self.log + 1):
			self.update(p >> i)

	def apply(self, l, r, f):
		assert 0 <= l and l <= r and (r <= self.n)
		if l == r:
			return
		l += self.size
		r += self.size
		for i in range(self.log, 0, -1):
			if l >> i << i != l:
				self.push(l >> i)
			if r >> i << i != r:
				self.push(r - 1 >> i)
		(l2, r2) = (l, r)
		while l < r:
			if l & 1:
				self.all_apply(l, f)
				l += 1
			if r & 1:
				r -= 1
				self.all_apply(r, f)
			l >>= 1
			r >>= 1
		(l, r) = (l2, r2)
		for i in range(1, self.log + 1):
			if l >> i << i != l:
				self.update(l >> i)
			if r >> i << i != r:
				self.update(r - 1 >> i)

	def max_right(self, l, g):
		assert 0 <= l and l <= self.n
		assert g(self.e)
		if l == self.n:
			return self.n
		l += self.size
		for i in range(self.log, 0, -1):
			self.push(l >> i)
		sm = self.e
		while 1:
			while i % 2 == 0:
				l >>= 1
			if not g(self.op(sm, self.d[l])):
				while l < self.size:
					self.push(l)
					l = 2 * l
					if g(self.op(sm, self.d[l])):
						sm = self.op(sm, self.d[l])
						l += 1
				return l - self.size
			sm = self.op(sm, self.d[l])
			l += 1
			if l & -l == l:
				break
		return self.n

	def min_left(self, r, g):
		assert 0 <= r and r <= self.n
		assert g(self.e)
		if r == 0:
			return 0
		r += self.size
		for i in range(self.log, 0, -1):
			self.push(r - 1 >> i)
		sm = self.e
		while 1:
			r -= 1
			while r > 1 and r % 2:
				r >>= 1
			if not g(self.op(self.d[r], sm)):
				while r < self.size:
					self.push(r)
					r = 2 * r + 1
					if g(self.op(self.d[r], sm)):
						sm = self.op(self.d[r], sm)
						r -= 1
				return r + 1 - self.size
			sm = self.op(self.d[r], sm)
			if r & -r == r:
				break
		return 0
(N, M) = list(map(int, input().split()))
seq = []
for i in range(N):
	(l, r) = list(map(int, input().split()))
	seq.append((l, r + 1))
seq.sort(key=lambda x: x[1] - x[0])
ans = [0 for i in range(M + 1)]
add = lambda x, y: x + y
INF = 10 ** 9
G = lazy_segtree([0 for i in range(M + 1)], max, -INF, add, add, 0)
stack = seq[::-1]
for d in range(1, M + 1):
	while len(stack) > 0 and stack[-1][1] - stack[-1][0] < d:
		(l, r) = stack[-1]
		G.apply(l, r, 1)
		stack.pop()
	ans[d] += len(stack)
	for i in range(0, M + 1, d):
		ans[d] += G.get(i)
for i in range(1, M + 1):
	print(ans[i])


import sys

def input():
	return sys.stdin.readline()[:-1]

class BIT:

	def __init__(self, size):
		self.table = [0 for _ in range(size + 2)]
		self.size = size

	def Sum(self, i):
		s = 0
		while i > 0:
			s += self.table[i]
			i -= i & -i
		return s

	def PointAdd(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += i & -i
		return

	def SegAdd(self, l, r, x):
		self.PointAdd(l, x)
		self.PointAdd(r + 1, -x)
		return
(n, m) = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(n)]
s.sort(key=lambda x: x[1] - x[0])
b = BIT(m)
too_long = n
cur = 0
for i in range(1, m + 1):
	while cur < n and s[cur][1] - s[cur][0] + 1 < i:
		too_long -= 1
		b.SegAdd(s[cur][0], s[cur][1], 1)
		cur += 1
	ans = too_long
	for j in range(i, m + 1, i):
		ans += b.Sum(j)
	print(ans)


import sys
input = sys.stdin.readline

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)
		self.base = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		self.base[i] += x
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

	def get(self, i):
		return self.base[i]

class RangeUpdate:

	def __init__(self, n):
		self.p = Bit(n + 1)
		self.q = Bit(n + 1)

	def add(self, s, t, x):
		t += 1
		self.p.add(s, -x * s)
		self.p.add(t, x * t)
		self.q.add(s, x)
		self.q.add(t, -x)

	def sum(self, s, t):
		t += 1
		return self.p.sum(t) + self.q.sum(t) * t - self.p.sum(s) - self.q.sum(s) * s

	def get(self, s):
		return self.p.get(s + 1) + self.q.get(s + 1) * (s + 1) + self.q.sum(s)
(n, m) = [int(i) for i in input().split()]
lr = [[int(i) for i in input().split()] for _ in range(n)]
lr.sort(key=lambda x: x[1] - x[0])
omiyage = RangeUpdate(m + 1)
index = 0
for d in range(1, m + 1):
	while index < n and lr[index][1] - lr[index][0] < d:
		omiyage.add(lr[index][0] + 1, lr[index][1] + 1, 1)
		index += 1
	ans = 0
	pos = 0
	while pos <= m:
		ans += omiyage.get(pos + 1)
		pos += d
	ans += n - index
	print(ans)


(N, M) = map(int, input().split())
D = [[] for i in range(M + 1)]
for i in range(N):
	(l, r) = map(int, input().split())
	D[r - l + 1].append(l)
data = [0] * (M + 2)

def get(k):
	s = 0
	while k:
		s += data[k]
		k -= k & -k
	return s

def add(k, x):
	while k <= M + 1:
		data[k] += x
		k += k & -k
C = N
ans = []
for d in range(1, M + 1):
	for l in D[d]:
		add(l, 1)
		add(l + d, -1)
		C -= 1
	cnt = C
	i = d
	while i <= M:
		cnt += get(i)
		i += d
	ans.append(cnt)
print(*ans, sep='\n')


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
C = [list(map(int, input().split())) for i in range(n)]

class Bit:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, l, r):
		s = 0
		while r > 0:
			s += self.tree[r]
			r -= r & -r
		while l > 0:
			s -= self.tree[l]
			l -= l & -l
		return s

	def add(self, i, x):
		i += 1
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

	def sett(self, i, x):
		self.add(i, x - self.sum(i, i + 1))

	def print_bit(self):
		print([self.sum(i, i + 1) for i in range(self.size)])

	def print_sum(self):
		print([self.sum(0, i + 1) for i in range(self.size)])

	def lower_bound_left(self, w):
		n = self.size
		r = 1
		x = 0
		if self.sum(0, n) < w:
			return n
		while r < n:
			r *= 2
		le = r
		while le > 0:
			if x + le < n and self.tree[x + le] < w:
				w -= self.tree[x + le]
				x += le
			le //= 2
		return x

	def upper_bound_left(self, w):
		n = self.size
		r = 1
		x = 0
		if self.sum(0, n) <= w:
			return n
		while r < n:
			r *= 2
		le = r
		while le > 0:
			if x + le < n and self.tree[x + le] <= w:
				w -= self.tree[x + le]
				x += le
			le //= 2
		return x

	def lower_bound_right(self, w):
		return self.upper_bound_left(w) - 1

	def upper_bound_right(self, w):
		return self.lower_bound_left(w) - 1
D = [[] for i in range(m + 1)]
for d in range(1, m + 1):
	for j in range(d, m + 1, d):
		D[j].append(d)
L = [0] * (m + 1)
for i in range(1, m + 1):
	for j in range(len(D[i])):
		L[D[i][j]] = i
A = [-1] * (m + 1)
B = Bit(m + 2)
E = [0] * (m + 1)
ANS = [0] * (m + 1)
C.sort(key=lambda x: x[1])
ind = 0
for i in range(1, m + 1):
	for j in range(len(D[i])):
		k = D[i][j]
		if A[k] != -1:
			ANS[k] += B.sum(0, A[k] + 1)
		E[i] += 1
		A[k] = i
	while ind < n and C[ind][1] <= i:
		l = C[ind][0]
		r = C[ind][1]
		B.add(l, 1)
		B.add(r + 1, -1)
		ind += 1
for i in range(1, m + 1):
	ANS[i] += B.sum(0, L[i] + 1)
for i in range(1, m + 1):
	print(ANS[i])


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
(n, m) = map(int, readline().split())
lr = list(map(int, read().split()))
imos = [0] * (m + 2)
ans = [0] * (m + 2)
it = iter(lr)
for (l, r) in zip(it, it):
	i = 1
	li = r + 1
	while li > i:
		ri = min(li, r // i + 1)
		li = (l - 1) // i + 1
		if ri > li:
			imos[li] += 1
			imos[ri] -= 1
		i += 1
	for i in range(1, li):
		if r // i - (l - 1) // i > 0:
			ans[i] += 1
for i in range(1, m + 1):
	imos[i] += imos[i - 1]
	ans[i] += imos[i]
print('\n'.join(map(str, ans[1:m + 1])))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

class BIT:

	def __init__(self, n):
		self.size = n
		self.tree = [0 for _ in range(n + 1)]
		self.p = 2 ** (n.bit_length() - 1)
		self.dep = n.bit_length()

	def get(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

	def bl(self, v):
		if v <= 0:
			return -1
		s = 0
		k = self.p
		for _ in range(self.dep):
			if s + k <= self.size and self.tree[s + k] < v:
				s += k
				v -= self.tree[s + k]
			k //= 2
		return s + 1

def main():
	(n, m) = map(int, input().split())
	lr = [tuple(map(int, input().split())) for _ in range(n)]
	bt = BIT(m)
	lr = list(sorted(lr, key=lambda x: x[1] - x[0]))
	i = 0
	for d in range(1, m + 1):
		for i in range(i, n):
			if lr[i][1] - lr[i][0] + 1 == d:
				bt.add(lr[i][0], 1)
				bt.add(lr[i][1] + 1, -1)
				if i == n - 1:
					i = n
					break
			else:
				break
		ans = n - i
		for j in range(d, m + 1, d):
			ans += bt.get(j)
		print(ans)
main()


class BIT:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def add(self, k, x):
		while k <= self.n:
			self.bit[k] += x
			k += k & -k

	def sum(self, k):
		s = 0
		while k > 0:
			s += self.bit[k]
			k -= k & -k
		return s
(n, m) = map(int, input().split())
st = BIT(m)
(L, R) = ([], [])
d = [[] for i in range(m + 1)]
for i in range(n):
	(l, r) = map(int, input().split())
	L.append(l)
	R.append(r)
	d[r - l + 1].append(i)
num = n
for i in range(1, m + 1):
	num -= len(d[i])
	for j in d[i]:
		st.add(L[j], 1)
		st.add(R[j] + 1, -1)
	tmp = 0
	k = i
	for j in range(k, m + 1, i):
		tmp += st.sum(j)
	print(num + tmp)


class BIT:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)
		self.depth = n.bit_length()
		self.n0 = 1 << self.depth

	def get_sum(self, i):
		s = 0
		i += 1
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def query(self, l, r):
		return self.get_sum(r) - self.get_sum(l - 1)

	def add(self, i, x):
		i += 1
		while i <= self.size:
			self.tree[i] += x
			i += i & -i

	def bisect_left(self, w):
		if w <= 0:
			return 0
		(x, k) = (0, self.n0)
		for _ in range(self.depth):
			k >>= 1
			if x + k <= self.size and self.tree[x + k] < w:
				w -= self.tree[x + k]
				x += k
		return x
import sys
read = sys.stdin.read
readline = sys.stdin.readline
(n, m, *lr) = map(int, read().split())
mp = iter(lr)
dlr = [(r - l + 1, l, r) for (l, r) in zip(mp, mp)]
dlr.sort(reverse=True)
ans = [0] * (m + 1)
b = BIT(m + 2)
for i in range(1, m + 1):
	while dlr and dlr[-1][0] < i:
		(d, l, r) = dlr.pop()
		b.add(l, 1)
		b.add(r + 1, -1)
	v = 0
	for j in range(i, m + 1, i):
		v += b.get_sum(j)
	ans[i] = len(dlr) + v
print(*ans[1:], sep='\n')


(N, M) = list(map(int, input().split()))
section = [[] for i in range(M + 1)]
for i in range(N):
	(l, r) = list(map(int, input().split()))
	section[r - l + 1].append((l, r))

def add(B, a, s):
	x = a
	while x <= len(B) - 1:
		B[x] += s
		x += x & -x

def sums(B, a):
	x = a
	S = 0
	while x != 0:
		S += B[x]
		x -= x & -x
	return S
Line = [0] * (M + 2)
K = N
for d in range(1, M + 1):
	for (l, r) in section[d]:
		add(Line, l, 1)
		add(Line, r + 1, -1)
		K -= 1
	ans = K
	for s in range(M // d + 1):
		ans += sums(Line, s * d)
	print(ans)


import sys
input = sys.stdin.readline
(N, M) = map(int, input().split())
a = []
for i in range(N):
	(l, r) = map(int, input().split())
	a.append((l, r))
a.sort(key=lambda x: x[0] - x[1])

class BIT:

	def __init__(self, n):
		self.n = n
		self.data = [0] * (n + 1)
		self.el = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		self.el[i] += x
		while i <= self.n:
			self.data[i] += x
			i += i & -i

	def get(self, i, j=None):
		if j is None:
			return self.el[i]
		return self.sum(j) - self.sum(i)

	def lowerbound(self, s):
		x = 0
		y = 0
		for i in range(self.n.bit_length(), -1, -1):
			k = x + (1 << i)
			if k <= self.n and y + self.data[k] < s:
				y += self.data[k]
				x += 1 << i
		return x + 1
fwk = BIT(M + 1)
for l in range(1, M + 1):
	res = len(a)
	for x in range(l, M + 1, l):
		res += fwk.sum(x)
	while len(a):
		if a[-1][1] - a[-1][0] <= l:
			fwk.add(a[-1][0], 1)
			fwk.add(a.pop()[1] + 1, -1)
		else:
			break
	print(res)