处理大数字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作为输入并且必须返回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

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

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,我们需要其他方法来找到大整数的平方根.这个问题可能会有所帮助.