Maximum Set (Codeforces 1796C)
Tags: Math, binary search

A set of positive integers $$$S$$$ is called beautiful if, for every two integers $$$x$$$ and $$$y$$$ from this set, either $$$x$$$ divides $$$y$$$ or $$$y$$$ divides $$$x$$$ (or both).You are given two integers $$$l$$$ and $$$r$$$. Consider all beautiful sets consisting of integers not less than $$$l$$$ and not greater than $$$r$$$. You have to print two numbers:  the maximum possible size of a beautiful set where all elements are from $$$l$$$ to $$$r$$$;  the number of beautiful sets consisting of integers from $$$l$$$ to $$$r$$$ with the maximum possible size. Since the second number can be very large, print it modulo $$$998244353$$$.

Input: The first line contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases.Each test case consists of one line containing two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 10^6$$$).

Output: For each test case, print two integers — the maximum possible size of a beautiful set consisting of integers from $$$l$$$ to $$$r$$$, and the number of such sets with maximum possible size. Since the second number can be very large, print it modulo $$$998244353$$$.

Note: In the first test case, the maximum possible size of a beautiful set with integers from $$$3$$$ to $$$11$$$ is $$$2$$$. There are $$$4$$$ such sets which have the maximum possible size:  $$$\{ 3, 6 \}$$$;  $$$\{ 3, 9 \}$$$;  $$$\{ 4, 8 \}$$$;  $$$\{ 5, 10 \}$$$. 

Sample Inputs:
4
3 11
13 37
1 22
4 100

Sample Outputs:
2 4
2 6
5 1
5 7

Solution (Python):
from collections import defaultdict
import math
from sys import stdin, stdout
import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
ninput = lambda : int(input())
sinput = lambda : input().decode().strip()
ainput = lambda : list(map(int, input().split()))
nprint = lambda x: stdout.write(str(x) + '\n')
sprint = lambda x: stdout.write(x + '\n')
aprint = lambda *x: stdout.write(' '.join(map(str, x)) + '\n')
t = ninput()
for i in range(t):
    (a, b) = ainput()
    maxi = 0
    sets = 0
    maxi = math.floor(math.log2(b / a)) + 1
    sets = math.floor(b / 2 ** (maxi - 1)) - a + 1
    num = math.floor(b / (2 ** (maxi - 2) * 3))
    if num >= a and num <= b:
        sets += (num - a + 1) * (maxi - 1)
    aprint(maxi, sets)

Solution (Python):
import math
import random
import sys
import os
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from bisect import *
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def I():
    return input()

def II():
    return int(input())

def MI():
    return map(int, input().split())

def LI():
    return list(input().split())

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

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LGMI():
    return list(map(lambda x: int(x) - 1, input().split()))
if sys.hexversion == 50924784:
    sys.stdin = open('stdin')

def solve():
    m = 998244353
    (l, r) = LII()
    a = int(math.log2(r / l)) + 1
    b = (a - 1) * (max(l, r // (2 ** (a - 2) * 3) + 1) - l)
    b += r // 2 ** (a - 1) + 1 - l
    print(a, int(b % m))
for t in range(II()):
    solve()

Solution (Python):
import math
import sys
input = sys.stdin.readline
import heapq

def put(arr, data):
    for i in arr:
        data[i] = data.get(i, 0) + 1
    return data

def inp():
    return int(input())

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

def insr():
    s = input()
    return list(s[:len(s) - 1])

def invr():
    return map(int, input().split())

def issubsequence(s1, s2):
    (n, m) = (len(s1), len(s2))
    (i, j) = (0, 0)
    while i < n and j < m:
        if s1[i] == s2[j]:
            i += 1
        j += 1
    return i == n
for _ in range(inp()):
    (m, n) = invr()
    ans1 = math.ceil(math.log2((n + 1) / m))
    print(ans1, end=' ')
    ans2 = 0
    maxer = math.floor(n / 2 ** (ans1 - 1))
    ans2 += maxer - m + 1
    kn = int(n * 2 / 3)
    maxer2 = math.floor(kn / 2 ** (ans1 - 1))
    if maxer2 >= m:
        ans2 += (maxer2 - m + 1) * (ans1 - 1)
    print(ans2 % 998244353)