题解：洛谷 B4356 [GESP202506 二级] 数三角形

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷B4356 [GESP202506 二级] 数三角形 - 洛谷【题目描述】直角三角形有两条直角边与一条斜边设两条直角边的长度分别为a , b a,ba,b则直角三角形的面积为a b 2 \frac{ab}{2}2ab​。请你计算当直角边长a , b a,ba,b均取不超过n nn的正整数时有多少个不同的面积为整数的直角三角形。直角边长分别为a , b a,ba,b和a ′ , b ′ a,ba′,b′的两个直角三角形相同当且仅当a a ′ , b b ′ aa, bbaa′,bb′或者a b ′ , b a ′ ab, baab′,ba′。【输入】一行一个整数n nn表示直角边长的最大值。【输出】输出一行一个整数表示不同的直角三角形数量。【输入样例】3【输出样例】3【核心思想】问题分析给定上限n nn求直角边长a , b ∈ [ 1 , n ] a, b \in [1, n]a,b∈[1,n]的不同直角三角形中面积为整数的个数。面积为a b 2 \frac{ab}{2}2ab​要求为整数即a b abab为偶数。由于( a , b ) (a,b)(a,b)和( b , a ) (b,a)(b,a)视为相同三角形需避免重复计数。这是一个枚举 奇偶性判定问题核心在于利用面积公式简化条件并控制枚举顺序去重。算法选择有序枚举去重令b bb从a aa开始枚举确保a ≤ b a \leq ba≤b避免( a , b ) (a,b)(a,b)和( b , a ) (b,a)(b,a)重复奇偶性判定a b m o d 2 0 ab \bmod 2 0abmod20时面积为整数关键步骤读入数据读取n nn有序枚举a aa从1 11到n nnb bb从a aa到n nn若a × b m o d 2 0 a \times b \bmod 2 0a×bmod20c n t ← c n t 1 cnt \leftarrow cnt 1cnt←cnt1输出结果c n t cntcnt时间/空间复杂度时间复杂度O ( n 2 ) O(n^2)O(n2)枚举所有满足1 ≤ a ≤ b ≤ n 1 \leq a \leq b \leq n1≤a≤b≤n的数对空间复杂度O ( 1 ) O(1)O(1)仅使用计数器枚举去重与奇偶性分析的核心思想面积整数条件转化a b 2 ∈ Z ⇔ a b ≡ 0 ( m o d 2 ) \frac{ab}{2} \in \mathbb{Z} \Leftrightarrow ab \equiv 0 \pmod{2}2ab​∈Z⇔ab≡0(mod2)即a aa和b bb中至少有一个为偶数将几何问题转化为数论问题有序枚举去重通过约束a ≤ b a \leq ba≤b每个无序对{ a , b } \{a,b\}{a,b}只被计数一次避免( 2 , 3 ) (2,3)(2,3)和( 3 , 2 ) (3,2)(3,2)的重复。若使用b bb从1 11到n nn枚举会导致重复计数乘法奇偶性两数乘积为偶数当且仅当至少一数为偶数因此只需检查a b m o d 2 ab \bmod 2abmod2即可无需分别判断a aa和b bb的奇偶性适用于组合计数、有序枚举去重类基础问题【算法标签】#入门 #语法基础【代码详解】#includebits/stdc.husingnamespacestd;intmain(){intn;// 输入的上限值intcnt0;// 计数器统计满足条件的数对个数cinn;// 输入正整数n// 外层循环遍历所有可能的a值1到nfor(inta1;an;a){// 内层循环遍历所有可能的b值a到nfor(intba;bn;b){// 检查a和b的乘积是否为偶数if(a*b%20)cnt;// 满足条件则计数器加1}}// 输出满足条件的数对总数coutcntendl;return0;}【运行结果】3 3