Task: | Rabbits |
Sender: | esya_rae |
Submission time: | 2024-11-27 17:17:58 +0200 |
Language: | Python3 (PyPy3) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.05 s | details |
#2 | ACCEPTED | 0.04 s | details |
#3 | ACCEPTED | 0.06 s | details |
#4 | ACCEPTED | 0.05 s | details |
#5 | ACCEPTED | 0.06 s | details |
#6 | ACCEPTED | 0.05 s | details |
#7 | ACCEPTED | 0.05 s | details |
#8 | ACCEPTED | 0.05 s | details |
#9 | ACCEPTED | 0.06 s | details |
#10 | ACCEPTED | 0.06 s | details |
#11 | ACCEPTED | 0.06 s | details |
#12 | ACCEPTED | 0.06 s | details |
#13 | ACCEPTED | 0.06 s | details |
#14 | ACCEPTED | 0.06 s | details |
#15 | ACCEPTED | 0.06 s | details |
#16 | ACCEPTED | 0.05 s | details |
#17 | ACCEPTED | 0.06 s | details |
#18 | ACCEPTED | 0.06 s | details |
#19 | ACCEPTED | 0.06 s | details |
#20 | ACCEPTED | 0.06 s | details |
#21 | ACCEPTED | 0.05 s | details |
#22 | ACCEPTED | 0.06 s | details |
#23 | ACCEPTED | 0.06 s | details |
Code
import sysimport mathsys.setrecursionlimit(10 ** 6)input = sys.stdin.readlinedef fib(a, b):fib = []for i in range(0, a):fib.append(1)for i in range(a, b + 1):fib.append((fib[-1] + fib[-a]))return fib[b]def fast_exp(m, n):if n == 0:return [[int(i == j) for i in range(len(m))] for j in range(len(m))]g = [[int(i == j) for i in range(len(m))] for j in range(len(m))]while n > 1:if n % 2 == 1:g = MM(g, m)n -= 1m = MM(m, m)n //= 2return MM(g, m)def MM(x, y):c = []for i in range(0, len(x)):temp = []for j in range(0, len(y[0])):s = 0for k in range(0, len(x[0])):s += (x[i][k] * y[k][j])temp.append(s)c.append(temp)return cdef create_f_m(a):m = []fr = [0] * afr[0], fr[-1] = 1, 1m.append(fr)for i in range(a - 1):r = [0] * ar[i] = 1m.append(r)return mdef fib(a, b):fib = []for i in range(0, a):fib.append(1)for i in range(a, b + 1):fib.append((fib[-1] + fib[-a]))return fib[b]m = create_f_m(2)a, b = map(int, input().split())L = -1R = int(math.log(a) + 10) * 10# print(R)while R - L > 1:M = (R + L) // 2fb = fast_exp(m, M)# print(fb[0][0])if fb[0][0] >= a:R = Melse:L = Mstart = R# print('start', start)L = start - 1R = int(math.log(b) + 10) * 10while R - L > 1:M = (R + L) // 2fb = fast_exp(m, M)if fb[0][0] > b:R = Melse:L = Mend = L# print('end', end)print(end - start + 1)
Test details
Test 1
Verdict: ACCEPTED
input |
---|
1 1000000000000000000000000000... |
correct output |
---|
480 |
user output |
---|
480 |
Test 2
Verdict: ACCEPTED
input |
---|
1 1 |
correct output |
---|
2 |
user output |
---|
2 |
Test 3
Verdict: ACCEPTED
input |
---|
100000000000000000000000000000... |
correct output |
---|
0 |
user output |
---|
0 |
Test 4
Verdict: ACCEPTED
input |
---|
708610693340620844512521044951... |
correct output |
---|
0 |
user output |
---|
0 |
Test 5
Verdict: ACCEPTED
input |
---|
786632967217302919379405189471... |
correct output |
---|
0 |
user output |
---|
0 |
Test 6
Verdict: ACCEPTED
input |
---|
636957196297222930779072940972... |
correct output |
---|
0 |
user output |
---|
0 |
Test 7
Verdict: ACCEPTED
input |
---|
114612974378925787282507968062... |
correct output |
---|
3 |
user output |
---|
3 |
Test 8
Verdict: ACCEPTED
input |
---|
702530369037899946705172780410... |
correct output |
---|
0 |
user output |
---|
0 |
Test 9
Verdict: ACCEPTED
input |
---|
274453166590443997807512962944... |
correct output |
---|
0 |
user output |
---|
0 |
Test 10
Verdict: ACCEPTED
input |
---|
855307457139726034048493902602... |
correct output |
---|
0 |
user output |
---|
0 |
Test 11
Verdict: ACCEPTED
input |
---|
639748223313530085297872188565... |
correct output |
---|
0 |
user output |
---|
0 |
Test 12
Verdict: ACCEPTED
input |
---|
432993801671766821076571962007... |
correct output |
---|
1 |
user output |
---|
1 |
Test 13
Verdict: ACCEPTED
input |
---|
879671727283213079665539196480... |
correct output |
---|
1 |
user output |
---|
1 |
Test 14
Verdict: ACCEPTED
input |
---|
667785392416865594397610159182... |
correct output |
---|
0 |
user output |
---|
0 |
Test 15
Verdict: ACCEPTED
input |
---|
781364162388340525444583784264... |
correct output |
---|
1 |
user output |
---|
1 |
Test 16
Verdict: ACCEPTED
input |
---|
655747298541157143247235560738... |
correct output |
---|
0 |
user output |
---|
0 |
Test 17
Verdict: ACCEPTED
input |
---|
403413620814634912261621439265... |
correct output |
---|
0 |
user output |
---|
0 |
Test 18
Verdict: ACCEPTED
input |
---|
447646307232291168178477866864... |
correct output |
---|
1 |
user output |
---|
1 |
Test 19
Verdict: ACCEPTED
input |
---|
295276605018840332007572176705... |
correct output |
---|
5 |
user output |
---|
5 |
Test 20
Verdict: ACCEPTED
input |
---|
443559664146440701189824727251... |
correct output |
---|
2 |
user output |
---|
2 |
Test 21
Verdict: ACCEPTED
input |
---|
734298173292503577661407215818... |
correct output |
---|
0 |
user output |
---|
0 |
Test 22
Verdict: ACCEPTED
input |
---|
864568133527920094870111453259... |
correct output |
---|
0 |
user output |
---|
0 |
Test 23
Verdict: ACCEPTED
input |
---|
352783378945989078522092015452... |
correct output |
---|
0 |
user output |
---|
0 |