一定数目的点或圆在等距离的排列下可以形成一个等边三角形这样的数被称为三角形数。前6个三角形数分别为136101521。给定一个正整数 x请你判断 x 能否表示为两个三角形数可以相同的和。c++最大数据10^9限时1s别用双指针和DP和二分

可以使用数学方法解决该问题。

首先，我们知道三角形数的递推公式为 T(n) = n * (n + 1) / 2。

假设 x = T(a) + T(b)，其中 a <= b。

我们可以将上述等式转化为 T(b) - T(a) = x。

根据三角形数的递推公式，我们可以得到 T(b) - T(a) = b * (b + 1) / 2 - a * (a + 1) / 2 = (b - a) * (b + a + 1) / 2。

因此，我们需要找到一个数 k，使得 x = k * (k + 1) / 2。

我们可以将上述等式转化为 2 * x = k * (k + 1)。

根据二次方程的性质，我们知道如果一个数是整数，那么它的平方根一定为整数或者无理数。

因此，我们只需要判断 2 * x 的平方根是否为整数即可。

如果是整数，那么 x 可以表示为两个三角形数的和；如果不是整数，那么 x 不能表示为两个三角形数的和。

下面是具体的实现代码：

#include <iostream>
#include <cmath>

bool isTriangleNumber(int x) {
    int n = sqrt(2 * x);
    return n * (n + 1) == 2 * x;
}

int main() {
    int x;
    std::cin >> x;
    if (isTriangleNumber(x)) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }
    return 0;
}

这样的实现方法时间复杂度为 O(1)，可以满足题目要求的时间限制