1796C.md (1582B)
1 Source: https://codeforces.com/problemset/problem/1796/C 2 3 C. Maximum Set 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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). 22 23 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: 24 25 * the maximum possible size of a beautiful set where all elements are from $l$ to $r$; 26 * the number of beautiful sets consisting of integers from $l$ to $r$ with the maximum possible size. 27 28 Since the second number can be very large, print it modulo $998244353$. 29 30 Input 31 32 The first line contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. 33 34 Each test case consists of one line containing two integers $l$ and $r$ ($1 \le l \le r \le 10^6$). 35 36 Output 37 38 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$. 39 40 Example 41 42 Input 43 44 ``` 45 4 46 47 3 11 48 49 13 37 50 51 1 22 52 53 4 100 54 ``` 55 56 Output 57 58 ``` 59 2 4 60 2 6 61 5 1 62 5 7 63 ``` 64 65 Note 66 67 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: 68 69 * $\{ 3, 6 \}$; 70 * $\{ 3, 9 \}$; 71 * $\{ 4, 8 \}$; 72 * $\{ 5, 10 \}$.