题目名称	1476. [UVa 11401] 数三角形
输入输出	`TricountUVa.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	20
题目来源	超级傲娇的AC酱于2014-01-09加入
开放分组	全部用户
提交状态
分类标签	数学递推 UVa
	分享题解

通过：84，提交：152，通过率：55.26%
Hzoi_Queuer	100	0.000 s	0.00 MiB	C++
Hzoi_chairman	100	0.000 s	0.00 MiB	C++
金身人面兽	100	0.000 s	0.00 MiB	C++
wow草原	100	0.000 s	0.00 MiB	C++
郑霁桓	100	0.000 s	0.00 MiB	C++
甘罗	100	0.001 s	0.17 MiB	Pascal
teacher	100	0.003 s	0.17 MiB	Pascal
赵赵赵	100	0.003 s	0.17 MiB	Pascal
洛克索耶夫	100	0.004 s	0.29 MiB	C++
喵喵喵	100	0.004 s	4.26 MiB	C++

关于数三角形的近10条评论(全部评论)
O（n）划过胡嘉兴 2017-11-21 17:58 8楼
回复 @洛克索耶夫 : bs不自己推QAQ 安呐一条小咸鱼。 2016-07-14 19:19 7楼
我有通项公式, 更何况此题数据这么水... 嘿嘿洛克索耶夫 2016-07-14 19:06 6楼
`if(i%2==0)a[i+1]=a[i]+(i-2)i/4; else a[i+1]=a[i]+(i-1)(i-1)/4;` 安呐一条小咸鱼。 2016-07-14 18:52 5楼
壮哉我大CJ直接在排列组合卷子上提供了通项公式。。。。。 n为偶数时 F(n)=n(n-2)(2n-5)/24 n为奇数时 F(n)=(n-1)(n-3)(2n-1)/24 Dijkstra 2014-06-25 18:11 4楼
原来递归没那么慢。。。早知道不用表了 ch3coooh 2014-03-07 19:57 3楼
长度爆了。。。我打了1000000行的表 ch3coooh 2014-03-07 19:36 2楼
注意方案数的大小。longlong(64int) 开起来。超级傲娇的AC酱 2014-01-09 02:17 1楼

1476. [UVa 11401] 数三角形

★★ 输入文件：TricountUVa.in 输出文件：TricountUVa.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

有多少种方法可以从 $1,2,3...,n$ 中选 $3$ 个不同的整数。使得以它们为三边长可以组成三角形？

比如 $n=5$ 时有 $3$ 种方法 $(2,3,4),(2,4,5),(3,4,5)$.$n=8$ 时有 $22$ 种方法。

【输入格式】

输入包含多组测试数据，每组测试数据为一行整数 $n(3 ≤ n ≤ 1 000 000)$。输入用 $n<3$ 的标志结束。

【输出格式】

对于每组数据，输出其方案数(每组占一行)

【样例输入】

5
8
1

【样例输出】

3
22

【提示】

数据组数不会超过 $20$ 组。

对于 $25\%$ 的数据：$(3≤n≤100)$

对于 $50\%$ 的数据：$(3≤n≤1 000)$

对于 $100\%$ 的数据：$(3≤n≤1 000 000)$

【来源】

$UVa$ $11401$ $Triangle$ $Counting$

刘汝佳，《算法竞赛入门经典训练指南》表$2.2$