LJJ爱数数
题目背景
题解请查看[https://www.cnblogs.com/Blog-of-Eden/p/9367521.html](https://www.cnblogs.com/Blog-of-Eden/p/9367521.html)
题目描述
PJY某次翻阅杂志时,看到一道题:
求出所有的**正整数**三元组{a,b,c},满足a,b,c<=n,**a,b,c三个数的最大公约数为1**,且**1/a+1/b=1/c**。
PJY嫌这道题太水,于是把它甩给了爱数数的LJJ,并加上了数据范围**n<=1e12**,让LJJ数出**有多少组满足条件的三元组{a,b,c}**
(注意当a不等于b时,{a,b,c}和{b,a,c}是不同的三元组,要算两次)
LJJ数到一半,发现这个数量太大了,于是他把问题抛给了你。请你输出这个数量。
输入输出格式
输入格式
输入仅一行:一个正整数n(n<=1e12)
输出格式
输出仅一行:一个整数,表示满足条件的三元组{a,b,c}的数量
输入输出样例
输入样例 #1
10
输出样例 #1
3
输入样例 #2
100
输出样例 #2
43
输入样例 #3
100000
输出样例 #3
42139
说明
20%:n<=2000
40%:n<=100000
60%:n<=10000000
80%:n<=1e9
100%:n<=1e12