codeforces-scrape

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

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 ```