eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Найбільша зростаюча підпослідовність

Найбільша зростаюча підпослідовність

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB

Розглянемо послідовність x_i, задану наступними співвідношеннями:

x_0 = a + b, x_1 = a – b,

x_i = (a·x_{i }_{- 2} + b·x_{i }_{- 1}) mod m, i > 1

Для заданого натурального n знайти довжину найбільшої зростаючої підпослідовності x_0, x_1, x_2, …, x_n.

Вхідні дані

Кожен тест складається з одного рядка, який містить чотири натуральних числа a, b, m, n (ab, 1a, b, m, n10^6). Кількість тестових випадків у одному тесті не перевищує 20.

Вихідні дані

Для кожного тесту в окремому рядку вивести довжину найбільшої зростаючої підпослідовності.

Приклад

Вхідні дані #1
3 1 20 10
5 2 1000 2000
Вихідні дані #1
5
70