Roads of Potokolandiya#189

Roads of Potokolandiya (Editorial)

Дороги задані правилом $i \leftrightarrow 2 i (mod n)$ i \leftrightarrow 2i \pmod n (де замість $0$ береться $n$ ). Виявляється, відповідь залежить лише від того, чи є $n$ степенем двійки.

Розберемося чому. Позначимо через $m$ непарну частину числа $n$ , тобто $n = 2^{s} \cdot m$ n = 2^s \cdot m, де $m$ непарне.

Подивимось на компоненту зв'язності міста $n$ . Ребро веде в $n$ з такого $i$ , що $2 i \equiv n$ 2i \equiv n, а це дає $i = n /2$ i = n/2 (якщо $n$ парне) або $i = n$ i = n. Тому з $n$ ми спускаємось у $n /2$ , далі в $n /4$ і так аж до $m$ . А з $m$ ребра ведуть у $2 m$ , $4 m$ , $\dots$ Неважко переконатися, що вся компонента міста $n$ складається виключно з кратних до $m$ .

Якщо $n$ не є степенем двійки, то $m > 1$ m > 1, і місто $1$ не кратне $m$ , тобто лежить в іншій компоненті. Отже, граф незв'язний, і парою міст без шляху можна впевнено назвати $1$ та $n$ .

Якщо ж $n = 2^{s}$ n = 2^s, то $m = 1$ m = 1, компонента міста $n$ містить кратні одиниці, тобто всі міста, — граф зв'язний.

Перевірка «чи є $n$ степенем двійки» робиться одним бітовим трюком: $n & (n - 1) = 0$ n \mathbin{\&} (n-1) = 0. Отже, весь розв'язок — одна умова, без жодного обходу графа, що важливо при $n \leq 1 0^{6}$ n \le 10^6.

Не забудьте про $n = 1$ n = 1: це степінь двійки, місто одне, відповідь YES.

i \leftrightarrow 2 i (mod n)

n = 2^{s} \cdot m

2 i \equiv n

i = n /2

i = n

m > 1

n = 2^{s}

m = 1

n & (n - 1) = 0

n \leq 1 0^{6}

n = 1