首页 > 代码库 > uva 11401 - Triangle Counting(数论)
uva 11401 - Triangle Counting(数论)
题目链接:uva 11401 - Triangle Counting
题目大意:有多少种方法可以从1,2,3...n中选出3个不同的数组成三角形,给出n,求种数。
解题思路:加法原理,设最大边为x的三角形有c(x)个,那么另外两条边长分别为y和z,根据三角形的形式可以的y+z>x,所以z的范围即为x?y<z<x
根据这个不等式可以得到每个y值所对应的z值个数,为等差数列,所以
c(x)=(x?1)?(x?2)2??x?12?2
然后根据递推:f(n)=∑i=1nc(i)
代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;
const int N = 1e6+5;
ll f[N];
int main () {
int n;
f[3] = 0;
for (ll i = 4; i < N; i++)
f[i] = f[i-1] + ((i-1)*(i-2)/2 - (i-1)/2)/2;
while (scanf("%d", &n) == 1 && n >= 3) {
printf("%llu\n", f[n]);
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。