Знайдіть кратні
Вам надано послідовність цифр 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 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, відповідно.