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
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:], i8), cache=True)
def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8), cache=True)
def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        i += i & -i

@njit((i8, i8[:]), cache=True)
def main(M, LR):
    L, R = LR[::2], LR[1::2]
    R = R + 1
    D = R - L
    argsort = np.argsort(D)
    L, R, D = L[argsort], R[argsort], D[argsort]
    idx = np.searchsorted(D, np.arange(M + 2))

    bit = np.zeros(M + 10, np.int64)
    rest = len(L)
    for d in range(1, M + 1):
        
        for i in range(idx[d], idx[d + 1]):
            rest -= 1
            add(bit, L[i], 1)
            add(bit, R[i], -1)
        ans = rest
        for n in range(d, M + 1, d):
            ans += get_sum(bit, n)
        print(ans)

N, M = map(int, readline().split())
LR = np.array(read().split(), np.int64)

main(M, LR)

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

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

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

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

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

if __name__ == "__main__":
  main()

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

if __name__ == "__main__":
  main()

Solution (Python):
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
  
  for l, r in LR:
    add(l, 1)
    add(r+1, -1)
  
  S = sorted([(r-l+1, l, r) for l, r in LR])
  cnt = 0
  L = []
  for i in range(m, 0, -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[::-1], sep="\n")

if __name__ == "__main__":
  main()

Solution (Python):
from operator import itemgetter
import sys
input = sys.stdin.buffer.readline


class BIT:
    """区間加算、一点取得クエリをそれぞれO(logN)で答えるデータ構造"""
    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 = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[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')

Solution (Python):
from operator import itemgetter
import sys
input = sys.stdin.readline


class BIT:
    """区間加算、一点取得クエリをそれぞれO(logN)で答えるデータ構造"""
    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 = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[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')

Solution (Python):
from operator import itemgetter
import sys
input = sys.stdin.readline


class BIT:
    """区間加算、一点取得クエリをそれぞれO(logN)で答えるデータ構造"""
    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 = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[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
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)
    print(cnt)

Solution (Python):
from operator import itemgetter
import sys
input = sys.stdin.readline


class BIT:
    """区間加算、一点取得クエリをそれぞれO(logN)で答えるデータ構造"""
    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 = i + 1
        s = 0
        while i <= self.n:
            s += self.bit[i]
            i += i & -i
        return s

    def add(self, l, r, val):
        """区間[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
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
    if d == 1:
        print(n)
        continue
    for i in range(0, m + 1, d):
        cnt += bit.get_val(i)
    print(cnt)

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

Solution (Python):
"""
BIT
区間[L,R]にxを加える。
座標Xでの値を求める。
"""
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)

Solution (Python):

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 = map(int,input().split())

BIT = [0] * (M+1)
dic = {}
for i in range(N):
    l,r = 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)))

Solution (Python):

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

Solution (Python):
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 = map(int, input().split())
    LRss = [[] for _ in range(M+1)]
    for _ in range(N):
        L, R = 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()

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

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


if __name__ == '__main__':
  main()

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

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

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


if __name__ == '__main__':
  main()

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

Solution (Python):
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=map(int,input().split())
L=[[] for i in range(M+1)]
bit=BIT(M+1)
for i in range(N):
    l,r=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)

Solution (Python):


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)

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

Solution (Python):
N,M=map(int,input().split())
section=[[] for i in range(M+1)]
for i in range(N):
  l,r=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)

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

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
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]

    print(ans + a)