问题 E: 【提高】仙人吃牛肉

问题 E: 【提高】仙人吃牛肉

题目描述

  

lxc是一个擅长吃的仙人,既然是仙人嘛,自然对吃的东西有一定的要求,比方说吃牛肉。 首先,lxc是非牦牛肉不吃的,其次,lxc每次只在3头牦牛中选1头来吃,并且这三头牦牛的长度还要满足以下条件:不妨设这三头牦牛的长度为a, b, c(a < b < c) ,则a*a+b*b=c*c。 lxc养了很多头牦牛,每头牦牛的长度都不大于N,每种长度的牦牛都有。作为lxc弟子的你想知道,一共有多少种不同的方案用来安排给lxc准备牦牛肉。即给定一个正整数N,找出符合a*a+b*b=c*c的三元组(a,b,c)的总数,其中a<b<c<=N。

输入

仅有一行包含一个正整数N(N <= 1000000)

输出

仅有一行包含一个整数,表示安排食谱的方案总数

样例输入输出

输入#1 复制
10
输出#1 复制
2

提示

样例说明 只有两种方案:a=3,b=4,c=5或a=6,b=8,c=10。 数据规模 30%的数据满足N<=300 60%的数据满足N<=20000 100%的数据满足N<=1000000

序号 标题 作者 发表时间 费用 订购数 操作