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 128 MiB

Рассмотрим целочисленную последовательность, состоящую из n элементов:

x[0] = a,

x[i] = ((x[i-1] * b + c) % m) + 1 для i = 1, 2, ... n - 1

Заданы числа a, b, c, m, n. Найти количество "последовательных подпоследовательностей", сумма чисел которых делится на m.

Рассмотрим пример, в котором a = 2, b = 1, c = 2, m = 4, n = 4. Тогда

x[0] = 2,

x[i] = (x[i-1] + 2) % 4 + 1, i = 1, 2, 3, 4

Откуда x[0] = 2, x[1] = 1, x[2] = 4, x[3] = 3. Последовательными подпоследовательностями будут {2}, {2 1}, {2 1 4}, {2 1 4 3}, {1}, {1 4}, {1 4 3}, {4}, {4 3} и {3}. Из перечисленных 10 подпоследовательностей сумма только двух делится на 4: {1, 4, 3} и {4}.

Giriş verilənləri

Первая строка содержит количество тестов t (t < 500). Каждая следующая строка является отдельным тестом и содержит пять целых чисел: a, b, c, m, n (0a, b, c1000, 0 < m, n10000).

Çıxış verilənləri

Для каждого теста в отдельной строке вывести его номер и требуемый результат.

Nümunə

Giriş verilənləri #1
2
2 1 2 4 4
923 278 195 8685 793
Çıxış verilənləri #1
Case 1: 2
Case 2: 34