P4844 LJJ爱数数

题解请查看 。

PJY 某次翻阅杂志时，看到一道题： 求出所有的 **正整数** 三元组 $(a,b,c)$，满足 $a,b,c \leq n$，**$\bold{a,b,c}$ 三个数的最大公约数为 $\bold{1}$**，且 **$\bold{\frac{1}{a}+\frac{1}{b}=\frac{1}{c}}$**。 PJY 嫌这道题太水，于是把它甩给了爱数数的 LJJ，并加上了数据范围 $\bold{n \leq 10^{12}}$，让 LJJ 数出 **有多少组满足条件的三元组 $\bold{(a,b,c)}$** （注意当 $a \not= b$ 时，$(a,b,c)$ 和 $(b,a,c)$ 是不同的三元组，要算两次） LJJ 数到一半，发现这个数量太大了，于是他把问题抛给了你。请你输出这个数量。

无

无

对于 $20\%$ 的数据，$n \leq 2 \times 10^{3}$。 对于 $40\%$ 的数据，$n \leq 10^{5}$。 对于 $60\%$ 的数据，$n \leq 10^{7}$。 对于 $80\%$ 的数据，$n \leq 10^{9}$。 对于 $100\%$ 的数据，$n \leq 10^{12}$。