Land plots#185

Land plots (Editorial)

Позначимо ширину $i$ -го стовпчика через $w_{i}$ w_i, а висоту $j$ -го рядка — через $h_{j}$ h_j. Тоді площа ділянки на перетині — це просто $w_{i} \cdot h_{j}$ w_i \cdot h_j.

Умова дає нам дві діагоналі:

a_{i} = w_{i} h_{i}, b_{i} = w_{i + 1} h_{i} .

a_i = w_i h_i, \qquad b_i = w_{i+1} h_i.

Поділивши друге на перше, отримуємо співвідношення сусідніх ширин:

\frac{w _{i + 1}}{w _{i}} = \frac{b _{i}}{a _{i}} .

\frac{w_{i+1}}{w_i} = \frac{b_i}{a_i}.

Тепер виразимо шукану площу. Нас цікавить $w_{p} h_{q}$ w_p h_q, а з першої рівності $h_{q} = a_{q} / w_{q}$ h_q = a_q / w_q, тому

w_{p} h_{q} = a_{q} \cdot \frac{w _{p}}{w _{q}} = a_{q} \cdot i = q \prod p - 1 \frac{b _{i}}{a _{i}} (p > q),

w_p h_q = a_q \cdot \frac{w_p}{w_q} = a_q \cdot \prod_{i=q}^{p-1} \frac{b_i}{a_i} \qquad (p > q),

і симетрично $a_{q} \cdot \prod_{i = p}^{q - 1} \frac{a _{i}}{b _{i}}$ a_q \cdot \prod_{i=p}^{q-1} \frac{a_i}{b_i} при $p < q$ p < q; при $p = q$ p = q відповідь дорівнює просто $a_{q}$ a_q.

Зверніть увагу, що самі $w_{i}$ w_i та $h_{j}$ h_j ми так і не знаходимо — вони можуть бути ірраціональними, — але їхній добуток завжди визначений однозначно.

Головна технічна складність — точність. Добуток дробів обчислювати в дійсних числах не можна, а чисельник і знаменник як цілі числа переповнять будь-який тип: це добуток до тисячі співмножників по $1 0^{9}$ 10^9. Саме тому умова й вимагає відповідь у факторизованому вигляді.

Тому працюємо одразу з розкладами на прості. Заведемо словник «просте $\to$ показник» і додамо до нього:

розклад $a_{q}$ a_q зі знаком плюс;
розклади всіх $b_{i}$ b_i (для $i$ від $q$ до $p - 1$ p-1) зі знаком плюс;
розклади всіх $a_{i}$ a_i (для того ж діапазону) зі знаком мінус.

Кожне число не перевищує $1 0^{9}$ 10^9, тому розкладається пробними діленнями за $O (1 0^{9}) \approx 3 \cdot 1 0^{4}$ \mathcal{O}(\sqrt{10^9}) \approx 3 \cdot 10^4 операцій; чисел щонайбільше $2 n \leq 2000$ 2n \le 2000, тому загальна складність — близько $6 \cdot 1 0^{7}$ 6 \cdot 10^7 операцій.

Наприкінці виводимо всі прості з ненульовим показником. Показники, що скоротилися до нуля, виводити не треба; за умовою відповідь коректна, тому від'ємних підсумкових показників не залишиться.