Submission #445758

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
445758	2021-07-19T13:42:21 Z	hamerin	Phibonacci (kriii2_P)	PyPy 3	4 / 4	47 ms	18464 KB

P

M = int(1e9 + 7)
mod = M**16


def ext_euc(a, b):
    if b == 0:
        return (a, 1, 0)
    g, x, y = ext_euc(b, a % b)
    return (g, y, x-(a//b)*y)


def matmul(l, r):
    return [[(l[0][0]*r[0][0]+l[0][1]*r[1][0]) % mod, (l[0][0]*r[0][1]+l[0][1]*r[1][1]) % mod],
            [(l[1][0]*r[0][0]+l[1][1]*r[1][0]) % mod, (l[1][0]*r[0][1]+l[1][1]*r[1][1]) % mod]]


def fibo(n):
    if n == -1:
        return 1

    base = [[1, 1], [1, 0]]
    target = [[1, 0], [0, 1]]
    while n:
        if n % 2:
            target = matmul(target, base)
        base = matmul(base, base)
        n //= 2

    return target[0][1]


N, K = map(int, input().split())

Fnk = fibo(N*K)
Fk = fibo(K)
Fnkm1 = fibo(N*K-1)
Fkm1 = fibo(K-1)

while Fk % M == 0 and Fnk % M == 0:
    Fk //= M
    Fnk //= M

A = (Fnk * ext_euc(Fk, mod)[1]) % M
B = (Fnkm1 - A * Fkm1) % M
print(A, B)

Subtask #1

1.0 / 1.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	42 ms	18212 KB	Output is correct
2	Correct	43 ms	18148 KB	Output is correct
3	Correct	42 ms	18212 KB	Output is correct
4	Correct	41 ms	18248 KB	Output is correct
5	Correct	41 ms	18212 KB	Output is correct
6	Correct	47 ms	18172 KB	Output is correct
7	Correct	41 ms	18212 KB	Output is correct
8	Correct	42 ms	18188 KB	Output is correct
9	Correct	40 ms	18196 KB	Output is correct
10	Correct	41 ms	18224 KB	Output is correct
11	Correct	41 ms	18164 KB	Output is correct
12	Correct	41 ms	18212 KB	Output is correct
13	Correct	42 ms	18216 KB	Output is correct
14	Correct	42 ms	18160 KB	Output is correct
15	Correct	42 ms	18208 KB	Output is correct
16	Correct	41 ms	18188 KB	Output is correct
17	Correct	41 ms	18212 KB	Output is correct
18	Correct	41 ms	18176 KB	Output is correct
19	Correct	41 ms	18128 KB	Output is correct
20	Correct	41 ms	18124 KB	Output is correct

Subtask #2

3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	47 ms	18316 KB	Output is correct
2	Correct	44 ms	18428 KB	Output is correct
3	Correct	43 ms	18420 KB	Output is correct
4	Correct	44 ms	18408 KB	Output is correct
5	Correct	43 ms	18364 KB	Output is correct
6	Correct	45 ms	18464 KB	Output is correct
7	Correct	45 ms	18372 KB	Output is correct
8	Correct	44 ms	18368 KB	Output is correct
9	Correct	44 ms	18440 KB	Output is correct
10	Correct	46 ms	18344 KB	Output is correct
11	Correct	44 ms	18340 KB	Output is correct
12	Correct	44 ms	18388 KB	Output is correct
13	Correct	44 ms	18376 KB	Output is correct
14	Correct	47 ms	18316 KB	Output is correct
15	Correct	45 ms	18420 KB	Output is correct
16	Correct	44 ms	18424 KB	Output is correct
17	Correct	44 ms	18376 KB	Output is correct
18	Correct	45 ms	18340 KB	Output is correct
19	Correct	44 ms	18312 KB	Output is correct
20	Correct	46 ms	18300 KB	Output is correct