UVa 11401 数三角形(组合数学)

数三角形(Triangle Counting, UVa 11401
有多少种方法可以从
1 23n中选出3个不同的整数, 使得以
它们为三边长可以组成三角形? 比如
n5时有3种方法, 即(23
4) , (235) , (345) 。 n8时有22种方法。
【输入格式】
输入包含多组测试数据, 每组数据的第一行为整数
n3≤n≤1000000) 。 输入用n3的标志结束。
170
【输出格式】
对于每组数据, 输出其方案总数。
【分析】
三重循环的时间复杂度为
On3) , 采用这种方法肯定超时。 这样的
规模即使是
On2) 时间的算法都很难承受, 那么只能进行一些数学分析
了。
用加法原理, 设最大边长为
x的三角形有cx) 个, 另外两条边长分
别为
yz, 根据三角形不等式[2]yzx。 所以z的范围是xyzx
根据这个不等式, 当
y1x1zx, 显然无解; y2时只有一个
解(
zx1) ; y3时有两个解(zx1或者zx2……直到yx
1时有x2个解。 根据等差数列求和公式, 一共有012+(x3
+(
x2) =(x1) (x2/2个解。
可惜, 这并不是
cx) 的正确数值, 因为上面的解包含了yz的情
况, 而且每个三角形算了两遍(想一想, 为什么) 。 解决方案很简单,
首先统计
yz的情况。 y的取值从x/21开始到x1为止, 一共有x1
x/2=(x1/2个解, 然后把这部分解扣除, 再除以2, 即
原题要求的实际上是
最大边长不超过n的三角形数目”fn) 。 根据
加法原理,
fn) =c1) +c2) +cn) 。 可以写成递推式

fn) =fn1) +cn) 。 代码如下。

#include
using namespace std;
long long f[1000010];
int main(){
	f[3]=0;
	for(long long x=4;x<=1000000;++x)
	f[x]=f[x-1]+((x-1)*(x-2)/2-(x-1)/2)/2;
	int n;
	while(cin>>n&&n>=3) cout<


未经允许不得转载!UVa 11401 数三角形(组合数学)