处理大数 python 2.7（运行时错误）

Question

我必须编写一个程序来找到以下无限序列中的第 n 个元素：

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

所以在这里你可以看到 'center' 递增一个，'center' 的边元素相互反映，所以我们可以把这个序列分成小组：

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

所以任务是在给定n的序列中找到第n个元素。例如我们输入7，必须return3，因为序列中的第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+1 中，它有 k*2+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 question 可能会有所帮助。

处理大数 python 2.7（运行时错误）

Handling large numbers python 2.7(runtime error)

python

algorithm

runtime