Fireworks
Contest: Codeforces Round 935 (Div. 3)
Difficulty rating: 900
Tags: math, number theory

One of the days of the hike coincided with a holiday, so in the evening at the camp, it was decided to arrange a festive fireworks display. For this purpose, the organizers of the hike bought two installations for launching fireworks and a huge number of shells for launching.

Both installations are turned on simultaneously. The first installation launches fireworks every $$$a$$$ minutes (i.e., after $$$a, 2 \cdot a, 3 \cdot a, \dots$$$ minutes after launch). The second installation launches fireworks every $$$b$$$ minutes (i.e., after $$$b, 2 \cdot b, 3 \cdot b, \dots$$$ minutes after launch).

Each firework is visible in the sky for $$$m + 1$$$ minutes after launch, i.e., if a firework was launched after $$$x$$$ minutes after the installations were turned on, it will be visible every minute from $$$x$$$ to $$$x + m$$$, inclusive. If one firework was launched $$$m$$$ minutes after another, both fireworks will be visible for one minute.

What is the maximum number of fireworks that could be seen in the sky at the same time?

Input format:
Each test consists of several test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then follow the descriptions of the test cases.

The first and only line of each test case contains integers $$$a$$$, $$$b$$$, $$$m$$$ ($$$1 \le a, b, m \le 10^{18}$$$) — the frequency of launching for the first installation, the second installation, and the time the firework is visible in the sky.

Output format:
For each set of input data, output a single number — the maximum number of fireworks that can be seen simultaneously.

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

Note:
In the first set of input data, the fireworks are visible in the sky for $$$5$$$ minutes. Since the first installation launches fireworks every $$$6$$$ minutes, and the second one every $$$7$$$ minutes, two fireworks launched from the same installation will not be visible in the sky at the same time. At the same time, after $$$7$$$ minutes from the start of the holiday, one firework from the first and one from the second camp will be visible. Thus, it is possible to see no more than $$$2$$$ fireworks simultaneously.

In the third set of input data, $$$17$$$ fireworks will be visible after $$$112$$$ minutes:

- $$$9$$$ fireworks launched from the first installation at times [$$$56, 63, 70, 77, 84, 91, 98, 105, 112$$$];
- $$$8$$$ fireworks launched from the second installation at times [$$$56, 64, 72, 80, 88, 96, 104, 112$$$].

Example input:
6
6 7 4
3 4 10
7 8 56
5 6 78123459896
1 1 1
1 1 1000000000000000000

Example output:
2
7
17
28645268630
4
2000000000000000002

Editorial:
Let's consider the moment in time $$$T = \text{LCM}(a, b)$$$ (least common multiple of numbers $$$a$$$ and $$$b$$$). It is easy to notice that since $$$T > 0$$$ and $$$T$$$ is divisible by both $$$a$$$ and $$$b$$$, at this moment both camps will release a firework, each of which will disappear after $$$m + 1$$$ minutes.
Let's look at the sky at the $$$T + m$$$-th minute. We will still see two fireworks released at the moment $$$T$$$, the first camp managed to release $$$\lfloor\frac{m}{a}\rfloor$$$ fireworks, and the second, similarly, $$$\lfloor\frac{m}{b}\rfloor$$$ fireworks (this follows from the fact that $$$T$$$ is divisible by $$$a$$$ and $$$b$$$). Taking into account the two fireworks released at the moment $$$T$$$, we will reach the answer $$$\lfloor\frac{m}{a}\rfloor + \lfloor\frac{m}{b}\rfloor + 2$$$.
Why can't we achieve a greater answer? Let's consider two setups for launching fireworks independently. Without loss of generality, consider the first setup (releasing fireworks every $$$a$$$ minutes). Consider the moment when the fireworks from this setup are visible in the sky. Let the first firework among the visible ones disappear at the moment $$$x$$$, then at the moment $$$x$$$ we will see no fewer fireworks, but at the moment $$$x + 1$$$ — fewer. At the moment $$$x$$$, there will be fireworks in the sky, released at moments [$$$x$$$, $$$x + a$$$, $$$\dots$$$, $$$x + a \cdot \lfloor\frac{m}{a}\rfloor$$$]. Thus, from the first setup, we can see no more than $$$\lfloor\frac{m}{a}\rfloor + 1$$$ fireworks simultaneously. The same formula is applicable to the second setup. We have proved that the answer does not exceed $$$\lfloor\frac{m}{a}\rfloor + 1 + \lfloor\frac{m}{b}\rfloor + 1 = \lfloor\frac{m}{a}\rfloor + \lfloor\frac{m}{b}\rfloor + 2$$$, so that is the answer.
Complexity: $$$\mathcal{O}(1)$$$.