题目描述
来源:Project Euler #585
热爱各种各样数学的 EntropyIncreaser 看到了一类根式化简题:
3+2+28+15+1520+96+1228+160+108=2+1=2+1=5+3=9+6+3−2=3+6+3−2=15+6+5−2
EntropyIncreaser 对这些傻逼题很感兴趣,他认为一个三元组 (x,y,z) 是好的,当且仅当 x+y+z 可以表示为 i=1∑ksiai 的形式,并且 si=±1,ai∈N∗,x∈[1,n],y,z∈/N。现在 EntropyIncreaser 想让身为蒟蒻的你,告诉他对于 n,所有好的三元组构成的根式化简得到的不同的值一共有多少个。
输入格式
一行一个整数 n。
输出格式
一行一个整数表示答案。
样例
5
3
数据范围与提示
对于 100% 的数据,1⩽n⩽5×105。