处理大数字 python 2.7(运行时错误)

Question

我必须创建一个程序，在以下无穷无尽的序列中找到第 n 个元素：

1 1 2 1 1 2 3 2 1 1 2 3 4 3 2 1......

所以

在这里你可以看到"中心"递增一个和"中心"的侧面元素相互反射，所以我们可以把这个序列分成几个小组：

[1][121][12321][1234321]..... 

因此，任务是在给定 n 的序列中找到第 n 个元素。例如，我们以 7 作为输入，必须返回 3，因为序列中的第 7 个元素是 3。这里的问题是，当n超过10^15我的程序显示运行时错误，而输入可以大到10^100000。这是我的代码：

n = int(input())
fin = n
number = long(1)
counter = long(0)
while n>0:
    n = n - number
    number = number+2
    counter = counter + 1
mid = long((counter-1)*(2+2*(counter-1))/2+1)
place = long(counter - abs(mid-fin))
if fin==0:
    print 0
else:
    print place

Answer 1

我们有一组数字：

[1] [1 2 1] [1 2 3 2 1] ...

k组中的总数为：

1 + 3 + 5 + ... + k*2-1 

这是一个算术级数，其总和等于

(1 + k*2-1) * k / 2 = k^2

现在让我们找到序列中第 n 个数字之前的完整组k的数量。

k = ⌊sqrt(n-1)⌋

现在我们知道我们的第 n 个数字位于具有k*2+1元素的组号 k+1 中。让我们先丢弃k组(它们有k^2个数字(，现在我们需要找到索引n-k^2的数字。它的值将等于 k+1 - |n-k^2 - (k+1)| .对于相对较小的n我们可以使用以下代码：

n = int(input())
k = int(math.sqrt(n-1))
print(k+1 - abs(n-k*k - (k+1)))

但是看到n <= 10^5000000约束我们不能简单地使用math.sqrt，我们需要其他方法来找到大整数的平方根。这个SO问题可能会有所帮助。