P16421 [IATI 2022] Divide

谁不喜欢数学呢 😊 设 $p$、$q$ 和 $n$ 为自然数。我们称一个自然数对 $(a, b)$ 是 **有趣的**，当且仅当满足以下条件： 1. $1 \le a \le p$ 2. $1 \le b \le q$ 3. $c = \frac{a \times b}{a + b}$ 是一个自然数，且 $1 \le c \le n$；也就是说，乘积 $a \times b$ 能被和 $a + b$ 整除，并且它们的商不超过 $n$。 本题的目标很简单——求**有趣的**数对的个数！ 请编写一个程序 `divide.cpp`，给定三个数 $p$、$q$ 和 $n$，计算出有趣的数对的数目。

标准输入的唯一一行包含整数 $p$、$q$ 和 $n$。

在标准输出的唯一一行中，输出有趣的数对的个数。数据保证答案小于 $10^{18}$。

### 数据范围 - $1 \le p, q, n \le 10^{10}$ ### 子任务 | 编号 | 附加约束 | 分值 | |:----:|:--------------------------|:-----:| | 1 | $1 \le p, q, n \le 2 \times 10^4$ | 5 | | 2 | $1 \le p, q, n \le 2.5 \times 10^7$ | 10 | | 3 | $1 \le p, q, n \le 2.5 \times 10^8$ | 10 | | 4 | $1 \le p, q, n \le 2 \times 10^9$ | 10 | | 5 | $n = 10^{10}$，且 $p = q$ | 10 | | 6 | $n = 10^{10}$ | 10 | | 7 | 无额外限制 | 45 | 翻译由 DeepSeek V4 Pro 完成