310520: CF1845F. Swimmers in the Pool
Description
There is a pool of length $l$ where $n$ swimmers plan to swim. People start swimming at the same time (at the time moment $0$), but you can assume that they take different lanes, so they don't interfere with each other.
Each person swims along the following route: they start at point $0$ and swim to point $l$ with constant speed (which is equal to $v_i$ units per second for the $i$-th swimmer). After reaching the point $l$, the swimmer instantly (in negligible time) turns back and starts swimming to the point $0$ with the same constant speed. After returning to the point $0$, the swimmer starts swimming to the point $l$, and so on.
Let's say that some real moment of time is a meeting moment if there are at least two swimmers that are in the same point of the pool at that moment of time (that point may be $0$ or $l$ as well as any other real point inside the pool).
The pool will be open for $t$ seconds. You have to calculate the number of meeting moments while the pool is open. Since the answer may be very large, print it modulo $10^9 + 7$.
InputThe first line contains two integers $l$ and $t$ ($1 \le l, t \le 10^9$) — the length of the pool and the duration of the process (in seconds).
The second line contains the single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of swimmers.
The third line contains $n$ integers $v_1, v_2, \dots, v_n$ ($1 \le v_i \le 2 \cdot 10^5$), where $v_i$ is the speed of the $i$-th swimmer. All $v_i$ are pairwise distinct.
OutputPrint one integer — the number of meeting moments (including moment $t$ if needed and excluding moment $0$), taken modulo $10^9 + 7$.
ExamplesInput9 18 2 1 2Output
3Input
12 13 3 4 2 6Output
10Input
1 1000000000 3 100000 150000 200000Output
997200007Note
In the first example, there are three meeting moments:
- moment $6$, during which both swimmers are in the point $6$;
- moment $12$, during which both swimmers are in the point $6$;
- and moment $18$, during which both swimmers are in the point $0$.
Input
题意翻译
## 题目描述 有 $n$ 个游泳者在长度为 $l$ 的水池中游泳。每个游泳者从时刻 $0$ 出发且互不干涉。 每个游泳者遵循以下路线：第 $i$ 个游泳者从位置 $0$ 开始游泳，以恒定的速度 $v_i$（每个单位时刻移动 $v_i$ 个单位长度）游到位置 $l$，到达后立即以相同的速度返回到位置 $0$。回到位置 $0$ 之后，立即重复以上过程。 当水池中（可为 $0,l$ 或任意其他水池中的位置）至少有 $2$ 个游泳者在相同位置时，我们把该时刻称为“相遇时刻”。 水池会开放 $t$ 时刻。求在 $t$ 时刻内相遇时刻的数量。输出答案对 $10^9+7$ 取模的结果。 ## 输入格式 输入文件共 $3$ 行。 输入第 $1$ 行，整数 $l,t$。 输入第 $2$ 行，整数 $n$。 输入第 $3$ 行，整数 $v_1,v_2,v_3,\dots,v_n$。保证 $v_i$ 两两不同。 ## 输出格式 输出在 $t$ 时刻内相遇时刻的数量对 $10^9+7$ 取模的结果。 ## 样例 \#1 解释 有 $3$ 个相遇时刻： - 时刻 $6$，两个游泳者都在位置 $6$； - 时刻 $12$，两个游泳者都在位置 $6$； - 时刻 $18$，两个游泳者都在位置 $0$。 ## 数据规模 对于 $100\%$ 的数据，$1 \le l,t \le 10^9$，$2 \le n \le 2 \times 10^5$，$1 \le v_i \le 2 \times 10^5$。其中 $i \in [1,n]$。 ------------ 译者：[$\color{#3498DB}{\textsf{\_Cppsteve\_}}$](https://www.luogu.com.cn/user/479296)Output
游泳池长度为 $ l $，有 $ n $ 个游泳者在游泳池里游泳。游泳者从时间点 0 同时开始游泳，每个游泳者在不同的泳道，因此他们之间不会相互干扰。每个游泳者从点 0 出发，以恒定速度 $ v_i $ 游到点 $ l $，然后瞬间转身以相同的速度游回点 0，如此往复。如果一个时刻至少有两个游泳者在游泳池的同一点，则称该时刻为相遇时刻。游泳池开放时间为 $ t $ 秒，需要计算开放时间内有多少个相遇时刻。答案可能非常大，所以输出对 $ 10^9 + 7 $ 取模的结果。
输入输出数据格式：
输入：
- 第一行包含两个整数 $ l $ 和 $ t $（$ 1 \le l, t \le 10^9 $），分别表示游泳池的长度和过程持续时间（秒）。
- 第二行包含一个整数 $ n $（$ 2 \le n \le 2 \cdot 10^5 $），表示游泳者的数量。
- 第三行包含 $ n $ 个整数 $ v_1, v_2, \dots, v_n $（$ 1 \le v_i \le 2 \cdot 10^5 $），其中 $ v_i $ 是第 $ i $ 个游泳者的速度。所有的 $ v_i $ 都是两两不同的。
输出：
- 输出一个整数，表示游泳池开放时间内的相遇时刻数量（如果需要，包括时刻 $ t $，但不包括时刻 0），结果对 $ 10^9 + 7 $ 取模。题目大意： 游泳池长度为 $ l $，有 $ n $ 个游泳者在游泳池里游泳。游泳者从时间点 0 同时开始游泳，每个游泳者在不同的泳道，因此他们之间不会相互干扰。每个游泳者从点 0 出发，以恒定速度 $ v_i $ 游到点 $ l $，然后瞬间转身以相同的速度游回点 0，如此往复。如果一个时刻至少有两个游泳者在游泳池的同一点，则称该时刻为相遇时刻。游泳池开放时间为 $ t $ 秒，需要计算开放时间内有多少个相遇时刻。答案可能非常大，所以输出对 $ 10^9 + 7 $ 取模的结果。 输入输出数据格式： 输入： - 第一行包含两个整数 $ l $ 和 $ t $（$ 1 \le l, t \le 10^9 $），分别表示游泳池的长度和过程持续时间（秒）。 - 第二行包含一个整数 $ n $（$ 2 \le n \le 2 \cdot 10^5 $），表示游泳者的数量。 - 第三行包含 $ n $ 个整数 $ v_1, v_2, \dots, v_n $（$ 1 \le v_i \le 2 \cdot 10^5 $），其中 $ v_i $ 是第 $ i $ 个游泳者的速度。所有的 $ v_i $ 都是两两不同的。 输出： - 输出一个整数，表示游泳池开放时间内的相遇时刻数量（如果需要，包括时刻 $ t $，但不包括时刻 0），结果对 $ 10^9 + 7 $ 取模。