c++ - 如何找到分形序列中的第 N 个数？

Question

作业是编写一个 C++ 程序，它接受输入数字 n 并输出序列中的第 n 个数字:

---

1 1 2 1 2 3 1 2 3 4 1 2 3 4 5 1 2 3 4 5 6 ...

这是我到目前为止想出的:

#include <iostream>
using namespace std;

int main()
{
    long long n,k=1,result;
    cin >> n;
    if(n==1){
        result=1;
    }else{
        for(int i=1,j=1;;i=j,j=j+k){
            if(n>i&&n<=j){
                result=n-i;
                break;
            }else{
                k++;
            }
        }
    }
    cout << result << endl;
}

这也是我之前写的:

#include <iostream>
using namespace std;

int main()
{
    long long n,count=0,result;
    cin >> n;
    for(int i=1;;i++){
        for(int j=1;j<=i;j++){
            count=count+1;
            if(count==n){
                result=j;
                break;
            }
        }
        if(count>=n){
            break;
        }
    }
    cout << result << endl;
}

这两个都适用于较小的数字，但问题是我必须遵循约束:

---

1 <= n <= 10^12

所以当输入更大的数字时，程序输出解决方案的时间太长并且超过了时间限制，即 2 秒。我已经为此工作了 5 个小时，但我不知道如何改进这些程序以使其更快。我还想到了一个可以帮助确定这样一个序列中的第 n 个数的特定公式，但我似乎无法在 Internet 或我的数学书籍中找到任何相关信息。有人可以指出我的解决方案吗？我将不胜感激。

Answer 1

我们可以按照您的顺序对数字进行分组:

(1) (1, 2) (1, 2, 3) ... 

数字的总量是

1 + 2 + 3 + ...

后者是等差级数，其和等于x*(x+1)/2 .

我们将找到完整组的数量 k在n+1之前- 序列中的第一个数字。 k等于最大整数使得 k*(k+1)/2 <= n .为了找到它，我们将求解二次方程:

x*(x+1)/2 = n 
x^2 + x - 2*n = 0

我们假设这个方程的正根是 x' .我们将其四舍五入为最接近的整数 k .如果x' == k (x' 是一个整数)就是答案。否则，答案是 n - k*(k+1)/2 .

示例 c++实现:

double d = 1 + 8.0 * n;
double x = (-1 + sqrt(d)) / 2;

long long k = floor(x);
long long m = k*(k+1) / 2;
if (m == n) {
    return k;
} else {
    return n - m;
}

解决方案有O(1)时间复杂度。