Постійні біти

WhatNext Software створює генератори послідовностей, які, як вони сподіваються, генеруватимуть досить випадкові послідовності 16-бітних беззнакових цілих чисел у діапазоні від $0$ до $65535$. Загалом, послідовність задається цілими числами $A$, $B$, $C$ та $S$, де 1 \leq A < 32768, 0 \leq B < 65536, 2 \leq C < 65536, та 0 \leq S < C. $S$ — це перший елемент (зерно) послідовності, а кожен наступний елемент генерується з попереднього. Якщо $X$ — елемент послідовності, тоді наступний елемент обчислюється за формулою

де $\mathrm{mod}$ — це залишок від ділення, або операція взяття по модулю. Хоча кожен елемент послідовності буде 16-бітним беззнаковим цілим числом, меншим за $65536$, проміжний результат A \times X + B може бути більшим, тому обчислення слід проводити з 32-бітним int, а не з 16-бітним short, щоб забезпечити коректність результату.

Деякі значення параметрів породжують кращі послідовності, ніж інші. Найбільш незручними для WhatNext Software є ті послідовності, в яких один або декілька бітів ніколи не змінюються. Біт, який не змінюється впродовж усієї послідовності — це стійкий біт (persistent). Ідеально, якщо у послідовності немає жодного стійкого біту. Ваше завдання — протестувати послідовність і визначити, які біти є стійкими.

Наприклад, особливо невдалий вибір — це A = 2, B = 5, C = 18, S = 3. Він породжує послідовність $3$, (2 \times 3 + 5) \bmod 18 = 11, (2 \times 11 + 5) \bmod 18 = 9, (2 \times 9 + 5) \bmod 18 = 5, (2 \times 5 + 5) \bmod 18 = 15, (2 \times 15 + 5) \bmod 18 = 17, далі (2 \times 17 + 5) \bmod 18 = 3 і повертаємось на початок. Тобто послідовність перебирає ті самі шість значень по колу:

Останній рядок таблиці позначає, які позиції бітів завжди $0$, завжди $1$ чи набувають обох значень у послідовності. Зверніть увагу, що $12$ з $16$ бітів є стійкими. (Добрі випадкові послідовності не мають стійких бітів, але обернене не завжди вірне. Наприклад, послідовність, визначена як A = 1, B = 1, C = 64000, S = 0, не містить стійких бітів, але також не є випадковою: вона просто відлічує від $0$ до $63999$ перед повторенням.) Зверніть увагу, що послідовність може не повертатися до зерна: при A = 2, B = 0, C = 16, S = 2 послідовність отримує $2$, $4$, $8$, $0$, $0$, $0$, $\dots$ .