Найдите кратные
Вам дана последовательность a_0a_1...a_{N−1} цифр и простое число Q. Для каждого i ≤ j с a_i ≠ 0, подпоследовательность a_ia_{i+1}...a_j может быть интерпретирована как десятичное представление положительного целого числа. Подпоследовательности с ведущими нулями не учитываются. Ваша задача — подсчитать количество пар (i, j), таких что соответствующая подпоследовательность делится на Q без остатка.
Входные данные
Входные данные состоят из не более чем 50 наборов данных. Каждый набор данных представлен строкой, содержащей четыре целых числа N, S, W и Q, разделённых пробелами, где 1 ≤ N ≤ 10^5, 1 ≤ S ≤ 10^9, 1 ≤ W ≤ 10^9, и Q — простое число меньше 10^8. Последовательность a_0...a_{N−1} длины N генерируется следующим кодом, в котором ai записывается как a[i].
int g = S; for(int i=0; i < N; i++) { a[i] = (g/7) % 10; if( g%2 == 0 ) { g = (g/2); } else { g = (g/2) ^ W; } }
Заметьте: операторы /, % и ^ — это целочисленное деление, остаток от деления и побитовое исключающее ИЛИ, соответственно. Приведённый код предназначен для генерации случайных чисел. Предполагаемое решение не зависит от способа генерации последовательности.
Конец ввода обозначается строкой, содержащей четыре нуля, разделённых пробелами.
Выходные данные
Для каждого набора данных выведите ответ в отдельной строке. Вы можете предположить, что ответ меньше 2^30.
Примечание к примеру: В первом наборе данных последовательность 421. Мы можем найти два числа, кратных Q = 7, а именно, 42 и 21.
Во втором наборе данных последовательность 5052, из которой мы можем найти 5, 50, 505 и 5, которые делятся на Q = 5. Обратите внимание, что мы не учитываем 0 или 05, так как они не являются допустимым представлением положительных чисел. Также обратите внимание, что мы считаем 5 дважды, так как он встречается дважды в разных позициях.
В третьем и четвёртом наборах данных последовательности 95073 и 12221, соответственно.