Раціональне наближення#6075

Раціональне наближення

1 секунда

64 мегабайти

Складна

Поліном $p (x)$ степеня $n$ може бути використаний для апроксимації функції $f (x)$ , підбираючи коефіцієнти $p (x)$ так, щоб вони відповідали першим $n$ коефіцієнтам степеневого ряду функції $f (x)$ (розкладеної навколо $x = 0$ x = 0). Наприклад,

На жаль, поліноми не завжди добре підходять для апроксимації функцій, які мають особливості. Щоб вирішити цю проблему, можна використовувати раціональні функції виду $p (x) / q (x)$ p(x)/q(x), де $p (x)$ і $q (x)$ є поліномами. Вас попросила Машина Апроксимаційних Обчислень вирішити цю задачу, щоб вони могли інтегрувати ваше рішення у своє програмне забезпечення для апроксимаційних обчислень.

Дано $m$ , $n$ і перші $m + n$ m+n коефіцієнтів степеневого ряду функції $f (x)$ . Потрібно обчислити два поліноми $p (x)$ і $q (x)$ степенів не більше $m - 1$ m-1 і $n - 1$ n-1 відповідно, такі, що степеневий ряд розкладу $q (x) \cdot f (x) - p (x)$ q(x) \cdot f(x) - p(x) має $0$ як свої перші $m + n - 1$ m+n-1 коефіцієнтів, і $1$ як свій коефіцієнт, що відповідає члену $x^{m + n - 1}$ x^{m+n-1}. Іншими словами, ми хочемо знайти $p (x)$ і $q (x)$ такі, що

де ... містить члени з степенями $x$ вищими за $m + n - 1$ m+n-1. З цього $f (x)$ може бути апроксимована як $p (x) / q (x)$ p(x)/q(x).

Фонові Визначення

Поліном $p (x)$ степеня $n$ може бути записаний як $p_{0} + p_{1} x + p_{2} x^{2} + \dots + p_{n} x^{n}$ p_0 + p_1x + p_2x^2 + \ldots + p_nx^n, де $p_{i}$ p_i є цілими числами в цій задачі.

Степеневий ряд розкладу $f (x)$ навколо $0$ може бути записаний як $f_{0} + f_{1} x + f_{2} x^{2} + \dots$ f_0 + f_1x + f_2x^2 + \ldots, де $f_{i}$ f_i є цілими числами в цій задачі.

Вхідні дані

Вхід складається з кількох випадків. Кожен випадок задається на одному рядку у формі $m$ $n$ $f_{0}$ f_0 $f_{1}$ f_1 $\dots$ $f_{m + n - 1}$ f_{m+n-1}, де $f_{i}$ f_i є коефіцієнтом $x^{i}$ x^i у степеневому ряді розкладу $f$ . Ви можете припустити, що $1 \leq m$ 1 \le m, $1 \leq n \leq 4$ 1 \le n \le 4, $2 \leq m + n \leq 10$ 2 \le m+n \le 10, і $f_{i}$ f_i є цілими числами такими, що $∣ f_{i} ∣ \leq 5$ |f_i| \le 5. Кінець вводу позначено рядком, що містить $m = n = 0$ m = n = 0, і без коефіцієнтів для $f$ . Ви можете припустити, що існує унікальне розв'язання для даного вводу.

Вихідні дані

Для кожного тестового випадку виведіть два рядки виходу. Виведіть поліном $p (x)$ на першому рядку, а потім $q (x)$ на другому рядку. Поліном $p (x)$ слід вивести як список пар $(p_{i}, i)$ (p_i, i), розташованих у порядку зростання $i$ , так що $p_{i}$ p_i є ненульовим коефіцієнтом для члена $x^{i}$ x^i. Кожен ненульовий коефіцієнт $p_{i}$ p_i слід вивести як $a / b$ , де $b > 0$ b > 0 і $a / b$ є коефіцієнтом, вираженим у нескоротному вигляді. Крім того, якщо $b = 1$ b = 1, то виведіть лише $a$ (і опустіть $b$ ). Якщо $p (x) = 0$ p(x) = 0, виведіть рядок, що містить лише $(0, 0)$ . Розділіть пари у списку одним пробілом. Поліном $q (x)$ слід вивести таким же чином. Вставте порожній рядок між випадками.

Приклади

Приклад 1