Відкриття#13087

Відкриття (Розбір)

Маємо такий факт:

a_{n} - a_{1} = a_{⌈ \frac{n}{2} ⌉}

a_n-a_1 = a_{\lceil \frac{n}{2} \rceil}

Підставивши це у вираз для арифметичної прогресії, отримуємо

(n - 1) m = a_{1} + (⌊ \frac{n}{2} ⌋) m

(n-1)m = a_1+(\lfloor \frac{n}{2} \rfloor)m

Можна використати бінарний пошук, оскільки функція зростає!

Складність $O (lo g (nm)$ .

Або ж просто продовжити розв'язання відносно $a_{1}$ :

a_{1} = (⌊ \frac{n}{2} ⌋) \times m

a_1 = (\lfloor \frac{n}{2} \rfloor) \times m

Складність — $O (1)$ .

a_{n} - a_{1} = a_{⌈ \frac{n}{2} ⌉}

(n - 1) m = a_{1} + (⌊ \frac{n}{2} ⌋) m

a_{1} = (⌊ \frac{n}{2} ⌋) \times m