G2019 [GESP202506 二级] 数三角形 题解

知识点：双重枚举、奇偶性、计数。

解题思路

枚举1≤a≤b≤n，三角形面积为ab/2，只有ab为偶数时面积为整数。

为什么正确

a≤b消除两条直角边交换产生的重复，偶数判断与整面积条件等价。

易错点

包含a==b的情况；计数用long long防止数量溢出。

复杂度

时间O(n²)，空间O(1)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    long long ans=0;
    for(int a=1;a<=n;a++)for(int b=a;b<=n;b++)ans+=(a*b%2==0);
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用8个自行生成的测试点。