codeforces-scrape

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

2044E.md (1272B)


      1 Source: https://codeforces.com/problemset/problem/2044/E
      2 
      3 E. Insane Problem
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Wave is given five integers $k$, $l_1$, $r_1$, $l_2$, and $r_2$. Wave wants you to help her count the number of ordered pairs $(x, y)$ such that all of the following are satisfied:
     22 
     23 * $l_1 \leq x \leq r_1$.
     24 * $l_2 \leq y \leq r_2$.
     25 * There exists a non-negative integer $n$ such that $\frac{y}{x} = k^n$.
     26 
     27 Input
     28 
     29 The first line contains an integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
     30 
     31 The only line of each test case contains five integers $k$, $l_1$, $r_1$, $l_2$, and $r_2$ ($2 \leq k \leq 10^9, 1 \leq l_1 \leq r_1 \leq 10^9, 1 \leq l_2 \leq r_2 \leq 10^9$).
     32 
     33 Output
     34 
     35 For each test case, output the number of matching ordered pairs $(x, y)$ on a new line.
     36 
     37 Example
     38 
     39 Input
     40 
     41 ```
     42 5
     43 
     44 2 2 6 2 12
     45 
     46 2 1 1000000000 1 1000000000
     47 
     48 3 5 7 15 63
     49 
     50 1000000000 1 5 6 1000000000
     51 
     52 15 17 78 2596 20914861
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 12
     59 1999999987
     60 6
     61 1
     62 197
     63 ```
     64 
     65 Note
     66 
     67 In the third test case, the matching ordered pairs are the following:
     68 
     69 * $(5,15)$
     70 * $(5,45)$
     71 * $(6,18)$
     72 * $(6,54)$
     73 * $(7,21)$
     74 * $(7,63)$
     75 
     76 In the fourth test case, the only valid ordered pair is $(1,1\,000\,000\,000)$