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

题目要求判断一个正整数x是否可以表示为两个三角形数的和。由于最大数据规模为10^9，限时1s，因此需要通过数学方法来解决这个问题。

观察三角形数的序列，可以发现每个三角形数都可以通过累加前面的自然数得到。即第n个三角形数T(n) = 1 + 2 + 3 + ... + n = n*(n+1)/2。

假设x可以表示为两个三角形数的和，即x = T(a) + T(b)，其中a和b为正整数。将等式两边都乘以2，得到2x = a*(a+1) + b*(b+1)。

将等式两边同时减去a*(a+1)，得到2x - a*(a+1) = b*(b+1)。我们可以将等式右边视作一个二次函数的形式，即y = b*(b+1)。根据二次函数的性质，当y递增时，b也是递增的。因此，我们可以通过二分查找的方法来确定b的值。

具体而言，我们遍历所有可能的a值，对于每个a，通过二分查找来确定b的值。如果找到了满足2x - a*(a+1) = b*(b+1)的b值，则说明x可以表示为两个三角形数的和。

以下是C++的代码实现：

#include <iostream>
using namespace std;

bool check(int x) {
    int left = 1, right = x;
    while (left <= right) {
        int mid = (left + right) / 2;
        int y = x - mid * (mid + 1) / 2;
        if (y < 0) {
            right = mid - 1;
        } else if (y == 0) {
            return true;
        } else {
            int b = (int)sqrt(y * 2);
            if (b * (b + 1) == y * 2) {
                return true;
            } else if (b * (b + 1) < y * 2) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    return false;
}

int main() {
    int x;
    cin >> x;
    if (check(x)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

该算法的时间复杂度为O(sqrt(x) * log(x))，可以在1秒内解决最大数据规模为10^9的问题