问题 L: Noblesse Code

内存限制：512 MB 时间限制：10 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：12 通过：3

You will be given

n

noblesse code pairs

(a_{1}, b_{1}), (a_{2}, b_{2}), \dots, (a_{n}, b_{n})

and

q

queries. In each query, you will be given a pair

(A, B)

, you need to figure out how many noblesse code pairs can be transformed from the given pair

(A, B)

. Every time you can transform the current pair

(A, B)

into

(A + B, B)

(A, A + B)

. You can do the transform operation for arbitrary times (or do nothing).

The first line contains a single integer $T$ ( $1 \leq T \leq 100$ ), the number of test cases. For each test case:

The first line of the input contains two integers $n$ and $q$ ( $1 \leq n, q \leq 50, 000$ ), denoting the number of noblesse code pairs and the number of queries.

In the next $n$ lines, the $i$ -th line contains two integers $a_{i}$ and $b_{i}$ ( $1 \leq a_{i}, b_{i} \leq 1e18$ ), describing the $i$ -th noblesse code pair.

In the next $q$ lines, the $i$ -th line contains two integers $A$ and $B$ ( $1 \leq A, B \leq 1e18$ ), describing the pair in the $i$ -th query.

It is guaranteed that the sum of all $n$ is at most $500, 000$ , and the sum of all $q$ is at most

For each query, print a single line containing an integer, denoting the number of noblesse code pairs that can be transformed from the given pair. Note that two noblesse code pairs

(a_{i}, b_{i}), (a_{j}, b_{j})

are considered to be different if and only if i

j

2023杭电多校

问题 L: Noblesse Code

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签

问题 L: Noblesse Code

题目描述

输入格式

输出格式

输入样例 复制

输出样例 复制

分类标签

输入样例复制

输出样例复制