SP6264 FNRANK - Rank of a Fraction

我们考虑一个分数集合，它由分数形式 $x/y$ 组成，满足条件 $0 \le x/y \le 1$，$y \le n$，并且 $x$ 和 $y$ 互素（即 $\gcd(x, y) = 1$）。 例如，当给定 $n = 5$ 时，这个集合中的分数按从小到大的顺序排列如下： $0/1$, $1/5$, $1/4$, $1/3$, $2/5$, $1/2$, $3/5$, $2/3$, $3/4$, $4/5$, $1/1$ 现在给定 $n$、$a$ 和 $b$，我们需要确定分数 $a/b$ 在上述有序分数集合中的排名。 ### 输入格式 输入的第一行是一个整数 $t$，表示测试用例的个数，其中 $t \le 20$。接下来的 $t$ 行，每行包含三个整数 $n$、$a$ 和 $b$，条件是 $n \le 100000$。 ### 输出格式 输出 $t$ 行，分别对应每个测试用例所计算的分数 $a/b$ 在集合中的排名。 ### 数据范围与提示 - $1 \le t \le 20$ - $1 \le n \le 100000$ - $0 \le a \le b \le n$ - $x$ 和 $y$ 互素，即 $\gcd(a, b) = 1$ ### 示例 **输入：** ``` 2 5 3 4 8 5 7 ``` **输出：** ``` 9 17 ``` 这个问题要求对于每个输入的测试用例，找到指定分数在按递增顺序排列的分数集合中的位置。每个答案都保证在整数范围内。 **本翻译由 AI 自动生成**

无

无