#1715. EntropyIncreaser 与 Galois 理论

EntropyIncreaser 与 Galois 理论

题目描述

来源:Project Euler #585

热爱各种各样数学的 EntropyIncreaser 看到了一类根式化简题:

$$\begin{aligned} \sqrt{3+\sqrt{2}+\sqrt{2}}&=\sqrt{2}+\sqrt{1}=\sqrt{2}+1\\ \sqrt{8+\sqrt{15}+\sqrt{15}}&=\sqrt{5}+\sqrt{3}\\ \sqrt{20+\sqrt{96}+\sqrt{12}}&=\sqrt{9}+\sqrt{6}+\sqrt{3}-\sqrt{2}=3+\sqrt{6}+\sqrt{3}-\sqrt{2}\\ \sqrt{28+\sqrt{160}+\sqrt{108}}&=\sqrt{15}+\sqrt{6}+\sqrt{5}-\sqrt{2} \end{aligned} $$

EntropyIncreaser 对这些傻逼题很感兴趣,他认为一个三元组 (x,y,z)(x,y,z) 是好的,当且仅当 x+y+z\sqrt{x+\sqrt{y}+\sqrt{z}} 可以表示为 i=1ksiai\displaystyle \sum_{i=1}^k s_i\sqrt{a_i} 的形式,并且 $s_i =\pm 1, a_i\in\mathbb N^*, x\in [1,n], \sqrt{y},\sqrt{z} \notin \mathbb N$。现在 EntropyIncreaser 想让身为蒟蒻的你,告诉他对于 nn所有好的三元组构成的根式化简得到的不同的值一共有多少个。

输入格式

一行一个整数 nn

输出格式

一行一个整数表示答案。

样例

5
3

数据范围与提示

对于 100%100\% 的数据,1n5×1051\leqslant n\leqslant 5\times 10^5