eolymp
bolt
Try our new interface for solving problems
Məsələlər

Слияние последовательностей

Слияние последовательностей

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Даны две бесконечные неубывающие последовательности A и B. Требуется найти k-ый элемент в неубывающей последовательности C, содержащей все элементы из A и B (включая повторы).

Последовательность A задается с помощью полинома P(x) = x^3:

a_1 = P(1) mod 12345, a_i = a_{i-1} + (P(i) mod 12345), при i > 1

Последовательность B задается с помощью полинома Q(x) = x^2:

b_1 = Q(1) mod 123, b_i = b_{i-1} + (Q(i) mod 123), при i > 1

Giriş verilənləri

Входной файл содержит натуральное число k (1k10^7).

Çıxış verilənləri

В выходной файл выведите одно число - ответ на задачу. Гарантируется, что ответ не превышает 2·10^9.

Nümunə

Giriş verilənləri #1
1        
Çıxış verilənləri #1
1