# Участник:Novitskiy97/Ascending Fibonacci Numbers Python

Перейти к: навигация, поиск

Python (PyPy 2.7.13)

```import sys
import re

text_splited = re.findall('\d+', text)
all_input_numbers = list(map(int, text_splited))
all_input_numbers.reverse()

f = [0] * 1100011

MAXN = 1100011
mod = 100000
f[0] = 1
f[1] = 0
for i in range(2, MAXN):
f[i] = (f[i-1] + f[i-2]) % mod

memory = [] # memory[i] -- counts of F[j], j from 0 to (i+1) * mod - 1
A = [0] * mod

for i in range(1, MAXN):
if i % mod == 0:
memory.append(A[:])
A[f[i]] += 1

def Print(a): # a[i] -- how many times need to print i
counter = 0
for i in range(mod):
for j in range(a[i]):
counter += 1
print(i),
if counter >= 100:
print('')
return
print('')

def simple_count(A, B):
a = [0] * mod
for i in range(A, B+1):
a[f[i]] += 1
return a

def count(A, B, trace=False):
l_block = A // mod
r_block = B // mod
if (r_block - l_block <= 1):
Print(simple_count(A, B))
return

l = simple_count(A, mod - 1)
r = simple_count((B // mod) * mod, B)
ml = memory[l_block]

mr = memory[r_block - 1]
z = [l[i] + r[i] + mr[i] - ml[i] for i in range(mod)]
Print(z)
return

t = all_input_numbers.pop()
for i in range(t):
a0 = all_input_numbers.pop()
a1 = all_input_numbers.pop()
print('Case %d:' % (i + 1)),
count(a0, a0+a1)```