Генератор псевдовипадкових чисел#9709

Генератор псевдовипадкових чисел

1 секунда

128 мегабайтів

Легка

Дональд любить природу. Будучи програмістом, він розробляє програми для імітації росту дерев та побудови реалістичних тривимірних ландшафтів. Для цих цілей Дональду необхідний надійний генератор псевдовипадкових чисел. Він пропонує наступний метод побудови нескінченної послідовності $40$ -бітних цілих чисел без знака.

m := 1 << 40 // = 2^40 = 1 099 511 627 776
S(0) := 0x600DCAFE // = 1 611 516 670
S(n + 1) := (S(n) + (S(n) >> 20) + 12345) % m

У останньому рядку операція $x >> 20$ x >> 20 означає цілу частину від евклідового ділення числа $x$ на $2^{20}$ 2^{20}, а операція $x % m$ — залишок від евклідового ділення числа $x$ на $m$ .

Як перший тест для оцінки якості генератора псевдовипадкових чисел Дональд хоче підрахувати кількість парних значень, породжених даною послідовністю, і перевірити, наскільки ця частка близька до $50%$ . Ваша допомога буде вельми доречна.

Вхідні дані

Одне ціле число $n (0 \leq n < 2^{63})$ n~(0 \le n < 2^{63}).

Вихідні дані

Виведіть одне ціле число — кількість парних значень серед елементів послідовності $S (0), S (1), ..., S (n - 1)$ S(0), S(1), ..., S(n - 1).

Приклади

Приклад 1

Приклад 2