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