Задачі
Найбільша зростаюча підпослідовність
Найбільша зростаюча підпослідовність
Розглянемо послідовність 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 (a ≥ b, 1 ≤ a, b, m, n ≤ 10^6). Кількість тестових випадків у одному тесті не перевищує 20.
Вихідні дані
Для кожного тесту в окремому рядку вивести довжину найбільшої зростаючої підпослідовності.
Приклад
Вхідні дані #1
3 1 20 10 5 2 1000 2000
Вихідні дані #1
5 70