B4356 [GESP202506 二级] 数三角形

题目重述

给定正整数 n，求直角边长 a, b 均不超过 n 的不同直角三角形的数量，要求三角形面积为整数。两个三角形相同当且仅当直角边相同（考虑顺序）。

解题思路

数学分析：
- 面积公式：S = (a×b)/2
- 要使 S 为整数，a×b 必须是偶数
- 即 a 和 b 中至少有一个是偶数
组合计算：
- 总对数：满足 a ≤ b ≤ n 的有序对数量为 n(n+1)/2
- 无效对数：a 和 b 均为奇数的对数
- 设 k = ?(n+1)/2? 为不超过 n 的奇数个数
- 无效对数为 k(k+1)/2
最终公式：
- 有效对数 = 总对数 - 无效对数

代码实现

CPP

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 计算总对数 C(n+1,2)
    long long total = 1LL * n * (n + 1) / 2;
    
    // 计算奇数个数
    int odd_count = (n + 1) / 2;
    
    // 计算无效对数（两个都是奇数）
    long long invalid = 1LL * odd_count * (odd_count + 1) / 2;
    
    cout << total - invalid << endl;
    return 0;
}

复杂度分析

时间复杂度：O(1)（直接公式计算）
空间复杂度：O(1)（仅使用常数空间）
希望管理员大大通过一下QwQ。

B4356 [GESP202506 二级] 数三角形

文章操作

B4356 [GESP202506 二级] 数三角形

题目重述

解题思路

代码实现

复杂度分析

相关推荐

评论

B4356 [GESP202506 二级] 数三角形