Swimmers in the Pool
Contest: Educational Codeforces Round 151 (Rated for Div. 2)
Difficulty rating: 2800
Tags: dp, fft, math, number theory

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$$$.

Input format:
The 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.

Output format:
Print one integer — the number of meeting moments (including moment $$$t$$$ if needed and excluding moment $$$0$$$), taken modulo $$$10^9 + 7$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
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$$$.

Example input:
9 18
2
1 2

Example output:
3

Example input:
12 13
3
4 2 6

Example output:
10

Editorial:
Firstly, note that there are two different situations when some two swimmers meet: they either move in the same direction, or in opposite directions.
Suppose, swimmers $$$i$$$ and $$$j$$$ meet while moving in the same direction. We can write some easy system of equation and get that they will meet each $$$\frac{2l}{|v_i - v_j|}$$$ seconds. Analogically, if they meet while moving in the opposite directions, they will meet each $$$\frac{2l}{v_i + v_j}$$$ seconds.
Let's create array $$$w$$$ that will contain all possible values $$$|v_i \pm v_j|$$$ exactly once. If $$$V = \max{v_i}$$$ then values $$$w_i \le 2V$$$ and we can calculate all of them using FFT fast multiplication two times: for sums $$$v_i + v_j$$$ and for differences $$$v_i - v_j$$$.
Okay, we got all possible $$$w_i$$$, how to calculate the answer. For a fixed value $$$w_i$$$ meeting moments are $$$\frac{2l \cdot k}{w_i}$$$ for all $$$k$$$ in segment $$$[1, k_i]$$$. $$$k_i$$$ is the upper bound and can be calculated as $$$k_i = \left\lfloor \frac{t \cdot w_i}{2l} \right\rfloor$$$.
We found that for each $$$w_i$$$ there are exactly $$$k_i$$$ meeting points, but since in one meeting moment more than two swimmers may meet we need to calculate each value $$$\frac{2l \cdot k}{w_i}$$$ exactly once.
Note that $$$\frac{2l \cdot k_1}{w_i} = \frac{2l \cdot k_2}{w_j}$$$ iff $$$\frac{k_1}{w_i} = \frac{k_2}{w_j}$$$. And we can rephrase our task as following: calculate the number of unique fractions $$$\frac{k}{w_i}$$$ where $$$1 \le k \le k_i$$$.
The key idea here is to calculate only irreducible fractions. Suppose we have fractions $$$\frac{1}{w_i}, \frac{2}{w_i}, \dots, \frac{k_i}{w_i}$$$. Let's add to the answer only irreducible fractions among them (we will discuss how to do it later). For any other fraction $$$\frac{k'}{w_i}$$$ $$$(k', w_i) = d > 1$$$ and $$$d$$$ is a divisor of $$$w_i$$$.
If we fix some divisor $$$d$$$ of $$$w_i$$$ there will be exactly $$$\left\lfloor \frac{k_i}{d} \right\rfloor$$$ fractions $$$\frac{k'}{w_i}$$$ with $$$d | (k', w_i)$$$. Moreover, numerators will also form a segment $$$[1, \frac{k_i}{d}]$$$. So, instead of calculating them now, we will just "pass" that task to $$$w_j = \frac{w_i}{d}$$$.
In total, we iterate $$$w_i$$$ in decreasing order, add only the number of irreducible fractions $$$\frac{k}{w_i}$$$ to the answer. Then iterate over all divisors $$$d$$$ of $$$w_i$$$ and "update" value $$$k_j$$$ for $$$w_j = \frac{w_i}{d}$$$ with value $$$\frac{k_i}{d}$$$.
How to calculate the number of irreducible fractions $$$\frac{k}{w_i}$$$ with $$$1 \le k \le k_i$$$? With Möbius function, of course: $$$$$$ ir_i = \sum_{d | w_i}{\mu(d) \left\lfloor \frac{k_i}{d} \right\rfloor} $$$$$$ since for each divisor $$$d$$$ of $$$w_i$$$ there are exactly $$$\left\lfloor \frac{k_i}{d} \right\rfloor$$$ fractions where $$$(k', w_i)$$$ is divisible by $$$d$$$.
Both passing calculations and Möbius inversion works in $$$O(\text{number of divisors}(w_i))$$$. And since we iterate over all $$$w_i \le 2 V$$$, the total complexity is $$$O(V \log V)$$$.
Both FFT and next part works in $$$O(V \log V)$$$, so the total complexity is $$$O(n + V \log V)$$$.
P.S.: If you note that if $$$w_j = \frac{w_i}{d}$$$ then $$$k_j$$$ is always equal to $$$\frac{k_i}{d}$$$ then you can not only simplify the part with "passing down calculations" but get rid of Möbius inversion at all, replacing it with Sieve-like two for-s iterations.