B4356 [GESP202506 二级] 数三角形

· · 题解

B4356 [GESP202506 二级] 数三角形

题目重述

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

解题思路

  1. 数学分析：

    • 面积公式：S = (a×b)/2
    • 要使 S 为整数，a×b 必须是偶数
    • 即 a 和 b 中至少有一个是偶数

  2. 组合计算：

    • 总对数：满足 a ≤ b ≤ n 的有序对数量为 n(n+1)/2
    • 无效对数：a 和 b 均为奇数的对数
    • 设 k = ?(n+1)/2? 为不超过 n 的奇数个数
    • 无效对数为 k(k+1)/2

  3. 最终公式：

    • 有效对数 = 总对数 - 无效对数

代码实现

#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;
}

复杂度分析