1342C.md (1260B)
1 Source: https://codeforces.com/problemset/problem/1342/C 2 3 C. Yet Another Counting Problem 4 5 time limit per test 6 7 3.5 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 You are given two integers $a$ and $b$, and $q$ queries. The $i$-th query consists of two numbers $l_i$ and $r_i$, and the answer to it is the number of integers $x$ such that $l_i \le x \le r_i$, and $((x \bmod a) \bmod b) \ne ((x \bmod b) \bmod a)$. Calculate the answer for each query. 22 23 Recall that $y \bmod z$ is the remainder of the division of $y$ by $z$. For example, $5 \bmod 3 = 2$, $7 \bmod 8 = 7$, $9 \bmod 4 = 1$, $9 \bmod 9 = 0$. 24 25 Input 26 27 The first line contains one integer $t$ ($1 \le t \le 100$) — the number of test cases. Then the test cases follow. 28 29 The first line of each test case contains three integers $a$, $b$ and $q$ ($1 \le a, b \le 200$; $1 \le q \le 500$). 30 31 Then $q$ lines follow, each containing two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le 10^{18}$) for the corresponding query. 32 33 Output 34 35 For each test case, print $q$ integers — the answers to the queries of this test case in the order they appear. 36 37 Example 38 39 Input 40 41 ``` 42 2 43 4 6 5 44 1 1 45 1 3 46 1 5 47 1 7 48 1 9 49 7 10 2 50 7 8 51 100 200 52 ``` 53 54 Output 55 56 ``` 57 0 0 0 2 4 58 0 91 59 ```