CF1967B2 Reverse Card (Hard Version)

两个版本是不同的问题。你可能需要阅读两个版本。只有当两个版本都被解决时，你才能进行 hack。 给定两个正整数 $n$，$m$。 计算满足以下条件的有序对 $(a, b)$ 的数量： - $1 \le a \le n$，$1 \le b \le m$； - $b \cdot \gcd(a, b)$ 是 $a + b$ 的倍数。

每个测试点包含多组测试数据。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来是每组测试数据的描述。 每组测试数据的第一行包含两个整数 $n$，$m$（$1 \le n, m \le 2 \cdot 10^6$）。 保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $2 \cdot 10^6$。

对于每组测试数据，输出一个整数，表示满足条件的有序对数量。

在第一个测试用例中，没有任何一对满足条件。 在第四个测试用例中，$(2,2)$、$(3,6)$、$(4,4)$、$(6,3)$、$(6,6)$、$(8,8)$ 满足条件。 由 ChatGPT 4.1 翻译