c++ - 将数字表示为两个三角数之和

Question

三角数或三角形数统计排列在等边三角形中的对象。
他们的公式是n(n + 1)/ 2。

我想写一个数字作为两个三角形数字的总和。 (24 = 21 + 3; 48 = 45 + 3)

我已经用C++编写了一些代码，对于较小的数字可以很好地做到这一点。但是随着N变大，它变得越来越慢，这使我认为我的代码效率低下或完全错误。因此，我要求提出建议。

我很乐意接受您的任何批评或想法。这是我想出的。

它生成数字“i”，并将x-i的值赋予“j”。它测试两个数字是否都是三角形的(iok，jok)，如果是，则将它们打印出来并结束。如果找不到这样的数字，则会显示“NO”。

#include <iostream>

using namespace std;

int main(){
    long long x;
    cin>>x;
    long long j,i;
    int iok,jok;
    long sum;
    long long n;

    for(i=1;i<=x;i++){
        iok=0;
        sum=0;
        for (n=1; sum<=i; n++)
        {
            sum = sum + n;
            if (sum==i)
                iok=1;
        }
        j=x-i;
        jok=0;
        sum=0;
        for (n=1; sum<=j; n++)
        {
            sum = sum + n;
            if (sum==j)
                jok=1;
        }
        if(jok && iok){
            cout<<i<<" "<<j;
            return 0;
        }
    }
    cout<<"NO";
    return 0;
}

Answer 1

您的算法的时间复杂度为O(n ^ 2)，但是您可以用一个循环，复杂度为O(n)来解决问题。对n进行迭代，创建第n个三角数，从输入中减去它，然后检查结果是否为三角数。 –托马斯·萨布利克