Problem:
 Score : 700 points    Problem Statement 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 1 3 3
1 2
2 3
3 3      Sample Output 1 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 .        Sample Input 2 7 9
1 7
5 9
5 7
5 9
1 1
6 8
3 4      Sample Output 2 7
6
6
5
4
5
5
3
2

Solution (Python):
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:
    """
    0-indexed
    
    bit = Bit(10)  
    bit.add(2, 10)
    print(bit.sum(5))  
    """

    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:
    """
    ・範囲すべての要素に加算
    ・ひとつの値を取得
    の2種類のクエリをO(logn)で処理
    """

    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")

Solution (Python):
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:
    """
    0-indexed
    
    bit = Bit(10)  
    bit.add(2, 10)
    print(bit.sum(5))  
    """
    def __init__(self, n):
        self.size = n
        self.tree = [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):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


class BitImos:
    """
    ・範囲すべての要素に加算
    ・ひとつの値を取得
    の2種類のクエリをO(logn)で処理
    """
    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")

Solution (Python):
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)

for d in range(1, M + 1):
    for l, r in D[d - 1]:
        N -= 1
        BIT.add(l, 1)
        BIT.add(r + 1, -1)

    ans = N
    for i in range(d, M + 1, d):
        ans += BIT.sum(i)
    print(ans)

Solution (Python):
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)

Solution (Python):

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')

Solution (Python):
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)
 
 
 
 
if __name__ == '__main__':
	main()

Solution (Python):
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())

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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, ri + 1, ri - li + 1))

    sects.sort(key=itemgetter(2))

    print(N)

    left = 0
    ft = FenwickTree(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, size):
        self.n = size
        self.data = [0]*(size + 1)

    def add(self, i, x):
        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

if __name__ == '__main__':
    solve()

Solution (Python):
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):
        ''' a[i] += x '''
        i += 1 

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

    def get_sum(self, r):
        ''' sum[a_0 .. a_r) '''
        res = 0

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

        return res


if __name__ == '__main__':
    solve()

Solution (Python):
class BIT():
    def __init__(self,size):
        self.size=size
        self.node=[0]*(size+1)

    def sum(self,idx):
        ret=0
        while idx>0:
            ret+=self.node[idx]
            idx-=idx&(-idx)
        return ret

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

n,m=map(int,raw_input().split())
L=[[] for _ in xrange(m+1)]
for i in xrange(n):
    l,r=map(int,raw_input().split())
    r+=1
    L[r-l].append(l)
bit=BIT(m+1)
total=0
for d in xrange(1,m+1):
    for l in L[d]:
        r=l+d
        bit.add(l,1)
        bit.add(r,-1)
    total+=len(L[d])
    ans=n-total
    now=0
    while now<=m:
        ans+=bit.sum(now)
        now+=d
    print(ans)

Solution (Python):
class BIT():
    def __init__(self,size):
        self.size=size
        self.node=[0]*(size+1)

    def sum(self,idx):
        ret=0
        while idx>0:
            ret+=self.node[idx]
            idx-=idx&(-idx)
        return ret

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

n,m=map(int,raw_input().split())
L=[[] for _ in xrange(m+1)]
for i in xrange(n):
    l,r=map(int,raw_input().split())
    r+=1
    L[r-l].append(l)
bit=BIT(m+1)
ans=n
total=0
for d in xrange(1,m+1):
    for l in L[d]:
        r=l+d
        bit.add(l,1)
        bit.add(r,-1)
    total+=len(L[d])
    ans=n-total
    now=0
    while now<=m:
        ans+=bit.sum(now)
        now+=d
    print(ans)