89
правок
Изменения
→Связь с многочленами (за O(k^2 \cdot \log n))
get_nth(n, a[], <tex>Q</tex>)
'''while''' n <tex>\geqslant</tex> k
'''for''' i = k <tex>\cdots</tex> '''to''' 2k - 1
a[i] = <tex>\sum\limits_{j = 1}^{k}</tex> -q[j] <tex>\cdot</tex> a[i - j]
<tex>R = Q(t) \cdot Q(-t)</tex>
'''filter ''' a[i] '''with ''' (i '''mod ''' 2 == n '''mod ''' 2)
<tex>Q = R(\sqrt{t})</tex>
n = n '''div ''' 2
'''return''' a[n]
