三角数是形如 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<int64_t>(x)</int64_t>,确保不溢出(注意输入类型检查) - 用整数开方:对
d >= 0,调用自定义或标准库的整数平方根(C++20 起有std::sqrt对int64_t无保证,仍需手动处理) - 推荐用
static_cast<int64_t>(std::sqrt(static_cast<long double>(d)))</long></int64_t>提升精度,再上下各检查 1 个整数
C++20 及以上:用 std::is_square 或手写整数 sqrt
C++20 没提供 std::is_square,但可手写一个安全的整数平方根函数,时间复杂度 O(log d),无浮点误差:
立即学习“C++免费学习笔记(深入)”;
int64_t isqrt(int64_t n) {
if (n < 0) return -1;
if (n == 0 || n == 1) return n;
int64_t lo = 1, hi = n / 2 + 1;
while (lo <= hi) {
int64_t mid = lo + (hi - lo) / 2;
int64_t sq = mid * mid;
if (sq == n) return mid;
if (sq < n) lo = mid + 1;
else hi = mid - 1;
}
return hi; // floor(sqrt(n))
}然后判定逻辑就干净了:
- 若
x ,直接返回 <code>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)或负解误认为有效。


















