codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 \}$.