三角数是形如 n(n+1)/2(n≥1)的整数,如1、3、6、10……;高效判定需解方程 n²+n−2x=0,要求判别式 Δ=1+8x 为非负完全平方数且其平方根为奇数,避免浮点误差应使用整数平方根并验证奇偶性。

什么是三角数,以及为什么不能用循环暴力判断
三角数是形如 n*(n+1)/2 的整数(n ≥ 1),比如 1、3、6、10、15……。暴力法从 1 开始试 k*(k+1)/2 == x,最坏要试 O(√x) 次,对大整数(比如 int64_t 范围内)明显太慢。
真正高效的判定,本质是解方程:若 x 是三角数,则存在正整数 n 满足 n² + n − 2x = 0。判别式 Δ = 1 + 8x 必须为完全平方数,且其平方根 s 必须是奇数(因为 n = (s − 1)/2 需为整数)。
用 sqrt 判定完全平方数的陷阱与修复
std::sqrt 返回 double,浮点精度在大整数(如接近 LLONG_MAX)时会出错,直接取整再平方可能误判。例如 x = 9223372036854775807,1 + 8*x 超过 double 精确整数表示范围(2⁵³),导致 round(sqrt(d)) 错误。
- 先计算判别式
d = 1 + 8 * static_cast,确保不溢出(注意输入类型检查)(x) - 用整数开方:对
d >= 0,调用自定义或标准库的整数平方根(C++20 起有std::sqrt对int64_t无保证,仍需手动处理) - 推荐用
static_cast提升精度,再上下各检查 1 个整数(std::sqrt(static_cast (d)))
C++20 及以上:用 std::is_square 或手写整数 sqrt
C++20 没提供 std::is_square,但可手写一个安全的整数平方根函数,时间复杂度 O(log d),无浮点误差:
int64_t isqrt(int64_t n) {
if (n <p>然后判定逻辑就干净了:</p>
- 若
x ,直接返回false - 计算
d = 1 + 8 * x;若溢出(如x > (INT64_MAX - 1) / 8),按需处理(如返回false或抛异常) - 令
s = isqrt(d),检查s * s == d且s % 2 == 1
边界与符号处理:负数、零、大整数溢出
三角数定义域是正整数,所以 x ≤ 0 直接返回 false。但实际编码中容易忽略输入类型——比如传入 unsigned int 却没做符号检查,或用 int 接收大值导致隐式溢出。
- 函数签名建议用
bool is_triangular(int64_t x),显式控制范围 - 计算
8 * x前先检查:if (x > (INT64_MAX - 1) / 8) return false; - 避免用
double中间变量存8*x—— 它无法精确表示所有int64_t值 - 测试用例至少覆盖:
1(true)、2(false)、1000000000000(true?查证)、INT64_MAX(应 false)
最易被忽略的是:判别式 1 + 8x 必须非负且为完全平方,且平方根必须奇数——漏掉奇偶性检查,会把 x = 0(对应 n = 0)或负解误认为有效。
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











