← 返回题目列表

Codeforces · 1342/C

C. 又一个计数问题

中文机器翻译题面 查看原题

给你两个整数 $$$a$$$ 和 $$$b$$$,以及 $$$q$$$ 查询。第 $$$i$$$ 查询由两个数字 $$$l_i$$$ 和 $$$r_i$$$ 组成,其答案是满足 $$$l_i \le x \le r_i$$$ 和 $$$((x \bmod a) \bmod b) \ne ((x \bmod b) \bmod a)$$$ 的整数 $$$x$$$ 的数量。计算每个查询的答案。

回想一下 $$$y \bmod z$$$ 是 $$$y$$$ 除以 $$$z$$$ 的余数。例如,$$$5 \bmod 3 = 2$$$、$$$7 \bmod 8 = 7$$$、$$$9 \bmod 4 = 1$$$、$$$9 \bmod 9 = 0$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。然后是测试用例。

每个测试用例的第一行包含三个整数 $$$a$$$、$$$b$$$ 和 $$$q$$$ ($$$1 \le a, b \le 200$$$; $$$1 \le q \le 500$$$)。

接下来是 $$$q$$$ 行,每行包含对应查询的两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le 10^{18}$$$)。

输出

对于每个测试用例,打印 $$$q$$$ 整数 - 该测试用例的查询的答案按照出现的顺序排列。

示例

输入 #1

2
4 6 5
1 1
1 3
1 5
1 7
1 9
7 10 2
7 8
100 200

输出 #1

0 0 0 2 4 
0 91