1342C. C. Yet Another Counting Problem

\r\n

CF1342C. Yet Another Counting Problem

\n

时限: 3.5 秒 | 内存: 256 MB | 输入: 标准输入 | 输出: 标准输出

\r\n

给定两个整数 $a$ 和 $b$，以及 $q$ 个询问。第 $i$ 个询问包含两个数 $l_i$ 和 $r_i$，你需要回答在区间 $l_i \\le x \\le r_i$ 内，有多少个整数 $x$ 满足 $((x \\bmod a) \\bmod b) \\ne ((x \\bmod b) \\bmod a)$。

\r\n

这里 $y \\bmod z$ 表示 $y$ 除以 $z$ 的余数。例如，$5 \\bmod 3 = 2$，$7 \\bmod 8 = 7$，$9 \\bmod 4 = 1$，$9 \\bmod 9 = 0$。

\r\n

输入格式

\r\n

第一行包含一个整数 $t$（$1 \\le t \\le 100$），表示测试用例的数量。接下来是 $t$ 组测试用例。

\r\n

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

\r\n

接下来的 $q$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \\le l_i \\le r_i \\le 10^{18}$），表示每个询问的区间。

\r\n

输出格式

\r\n

对于每组测试用例，按输入顺序输出 $q$ 个整数，分别表示每个询问的答案。

\n

样例输入 1

\n

2\n4 6 5\n1 1\n1 3\n1 5\n1 7\n1 9\n7 10 2\n7 8\n100 200

\n

样例输出 1

\n

0 0 0 2 4 \n0 91

状态	递交者	时间	内存	语言	代码	递交时间
AC	dyh	357ms	1.7 MiB	C++20(O2)	1.1 KiB	2026-10-6 20:37:05
AC	汤音同	691ms	1.4 MiB	C++17(O2)	689 Bytes	2026-8-7 18:53:08

统计

递交统计

1342C. C. Yet Another Counting Problem

信息

还没有账户？

登录