题意

输入\(n\)，输出有多少种方法可以从\(1,2,3,\dots,n\)中选出3个不同的整数，使得以他们为三边长可以组成三角形。

\(n \leq 10^6\)

分析

参照刘汝佳的题解。

按最大边长分类统计，减去选了两个相同整数的非法情况，最后除2解决算了两次的问题。

递推预处理即可。

代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<algorithm>

#include<bitset>

#include<cassert>

#include<ctime>

#include<cstring>

#define rg register

#define il inline

#define co const

template<class T>il T read()

{

	rg T data=0;

	rg int w=1;

	rg char ch=getchar();

	while(!isdigit(ch))

	{

		if(ch=='-')

			w=-1;

		ch=getchar();

	}

	while(isdigit(ch))

	{

		data=data*10+ch-'0';

		ch=getchar();

	}

	return data*w;

}

template<class T>T read(T&x)

{

	return x=read<T>();

}

using namespace std;

typedef long long ll;

co int MAXN=1e6+7;

ll f[MAXN];

int main()

{

//	freopen(".in","r",stdin);

//	freopen(".out","w",stdout);

	f[3]=0;

	for(ll x=4;x<=1e6;++x)

		f[x]=f[x-1]+((x-1)*(x-2)/2-(x-1)/2)/2;

	int n;

	while(read(n)>=3)

		printf("%lld\n",f[n]);

	return 0;

}