Plus Minus Permutation
Contest: Codeforces Round 895 (Div. 3)
Difficulty rating: 1200
Tags: math

You are given $$$3$$$ integers — $$$n$$$, $$$x$$$, $$$y$$$. Let's call the score of a permutation$$$^\dagger$$$ $$$p_1, \ldots, p_n$$$ the following value:

$$$$$$(p_{1 \cdot x} + p_{2 \cdot x} + \ldots + p_{\lfloor \frac{n}{x} \rfloor \cdot x}) - (p_{1 \cdot y} + p_{2 \cdot y} + \ldots + p_{\lfloor \frac{n}{y} \rfloor \cdot y})$$$$$$

In other words, the score of a permutation is the sum of $$$p_i$$$ for all indices $$$i$$$ divisible by $$$x$$$, minus the sum of $$$p_i$$$ for all indices $$$i$$$ divisible by $$$y$$$.

You need to find the maximum possible score among all permutations of length $$$n$$$.

For example, if $$$n = 7$$$, $$$x = 2$$$, $$$y = 3$$$, the maximum score is achieved by the permutation $$$[2,\color{red}{\underline{\color{black}{6}}},\color{blue}{\underline{\color{black}{1}}},\color{red}{\underline{\color{black}{7}}},5,\color{blue}{\underline{\color{red}{\underline{\color{black}{4}}}}},3]$$$ and is equal to $$$(6 + 7 + 4) - (1 + 4) = 17 - 5 = 12$$$.

$$$^\dagger$$$ A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in any order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation (the number $$$2$$$ appears twice in the array) and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$, but the array contains $$$4$$$).

Input format:
The first line of input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Then follows the description of each test case.

The only line of each test case description contains $$$3$$$ integers $$$n$$$, $$$x$$$, $$$y$$$ ($$$1 \le n \le 10^9$$$, $$$1 \le x, y \le n$$$).

Output format:
For each test case, output a single integer — the maximum score among all permutations of length $$$n$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The first test case is explained in the problem statement above.

In the second test case, one of the optimal permutations will be $$$[12,11,\color{blue}{\underline{\color{black}{2}}},4,8,\color{blue}{\underline{\color{red}{\underline{\color{black}{9}}}}},10,6,\color{blue}{\underline{\color{black}{1}}},5,3,\color{blue}{\underline{\color{red}{\underline{\color{black}{7}}}}}]$$$. The score of this permutation is $$$(9 + 7) - (2 + 9 + 1 + 7) = -3$$$. It can be shown that a score greater than $$$-3$$$ can not be achieved. Note that the answer to the problem can be negative.

In the third test case, the score of the permutation will be $$$(p_1 + p_2 + \ldots + p_9) - p_9$$$. One of the optimal permutations for this case is $$$[9, 8, 7, 6, 5, 4, 3, 2, 1]$$$, and its score is $$$44$$$. It can be shown that a score greater than $$$44$$$ can not be achieved.

In the fourth test case, $$$x = y$$$, so the score of any permutation will be $$$0$$$.

Example input:
8
7 2 3
12 6 3
9 1 9
2 2 2
100 20 50
24 4 6
1000000000 5575 25450
4 4 1

Example output:
12
-3
44
0
393
87
179179179436104
-6

Editorial:
Let's call a number red if it is divisible by $$$x$$$.
Let's call a number blue if it is divisible by $$$y$$$.
Let's call a number purple if it is both red and blue at the same time.
The score of a permutation, by definition, is the sum of $$$p_i$$$ for all red numbers $$$i$$$ from $$$1$$$ to $$$n$$$, minus the sum of $$$p_i$$$ for all blue numbers $$$i$$$ from $$$1$$$ to $$$n$$$.
It is easy to see that $$$p_i$$$ at purple indices $$$i$$$ does not affect the score of the permutation: they are included in the sum once with a plus sign and once with a minus sign.
Therefore, the score of the permutation is the sum of $$$p_i$$$ for "red but not purple indices" minus the sum of $$$p_i$$$ for "blue but not purple indices".
Notice that the set of "red but not purple indices" and the set of "blue but not purple indices" cannot intersect, because if they had a common index, it would be purple.
Therefore, it is obviously optimal to place the largest numbers possible on "red but not purple indices" and the smallest numbers possible on "blue but not purple indices".
To calculate the number of indices that are "red but not purple", we can calculate the number of red indices and subtract the number of purple indices.
The number of red indices is $$$\lfloor \frac{n}{x} \rfloor$$$, and the number of blue indices is calculated similarly.
To calculate the number of purple indices, we need to notice that the condition "index is divisible by both $$$x$$$ and $$$y$$$" is equivalent to "index is divisible by $$$\operatorname{lcm}(x, y)$$$", where $$$\operatorname{lcm}$$$ denotes the least common multiple. Therefore, the number of purple indices is $$$\lfloor \frac{n}{\operatorname{lcm}(x, y)} \rfloor$$$.
Let $$$R$$$ be the number of "red but not purple" indices, and let $$$B$$$ be the number of "blue but not purple" indices. Then it is not difficult to see that the maximum score is $$$(n + (n - 1) + \ldots + (n - (R - 1)) - (1 + 2 + \ldots + B)$$$.
To quickly find this sum, we can use the formula for the sum of an arithmetic progression: $$$l + (l + 1) + \ldots + r = \frac{(l + r) \cdot (r - l + 1)}{2}$$$