Ланцюгові дроби

Ланцюговий дріб — це представлення дійсного числа у вигляді особливої збіжної послідовності раціональних чисел. Вони корисні у змагальному програмуванні, бо їх легко обчислювати і їх можна ефективно використовувати для пошуку найкращого можливого раціонального наближення відповідного дійсного числа (серед усіх чисел, знаменник яких не перевищує заданого значення).

Окрім того, ланцюгові дроби тісно пов'язані з алгоритмом Евкліда, що робить їх корисними в низці задач теорії чисел.

Представлення ланцюговим дробом

Означення

Нехай $a_0, a_1, \dots, a_k \in \mathbb Z$ і $a_1, a_2, \dots, a_k \geq 1$. Тоді вираз

$$r=a_0 + \frac{1}{a_1 + \frac{1}{\dots + \frac{1}{a_k}}},$$

називається представленням раціонального числа $r$ ланцюговим дробом і коротко позначається як $r=[a_0;a_1,a_2,\dots,a_k]$.

Приклад

Нехай $r = \frac{5}{3}$. Існує два способи представити його у вигляді ланцюгового дробу:

$$\begin{align} r = [1;1,1,1] &= 1+\frac{1}{1+\frac{1}{1+\frac{1}{1}}},\\ r = [1;1,2] &= 1+\frac{1}{1+\frac{1}{2}}. \end{align}$$

Можна довести, що будь-яке раціональне число можна представити ланцюговим дробом рівно $2$ способами:

$$r = [a_0;a_1,\dots,a_k,1] = [a_0;a_1,\dots,a_k+1].$$

Понад те, довжина $k$ такого ланцюгового дробу оцінюється як $k = O(\log \min(p, q))$ для $r=\frac{p}{q}$.

Міркування, що стоять за цим, стануть зрозумілими, щойно ми заглибимося в деталі побудови ланцюгового дробу.

Означення

Нехай $a_0,a_1,a_2, \dots$ — цілочислова послідовність така, що $a_1, a_2, \dots \geq 1$. Нехай $r_k = [a_0; a_1, \dots, a_k]$. Тоді вираз

$$r = a_0 + \frac{1}{a_1 + \frac{1}{a_2+\dots}} = \lim\limits_{k \to \infty} r_k.$$

називається представленням ірраціонального числа $r$ ланцюговим дробом і коротко позначається як $r = [a_0;a_1,a_2,\dots]$.

Зауважимо, що для $r=[a_0;a_1,\dots]$ і цілого $k$ виконується $r+k = [a_0+k; a_1, \dots]$.

Інше важливе спостереження: $\frac{1}{r}=[0;a_0, a_1, \dots]$ коли $a_0 > 0$ і $\frac{1}{r} = [a_1; a_2, \dots]$ коли $a_0 = 0$.

Означення

У наведеному вище означенні раціональні числа $r_0, r_1, r_2, \dots$ називаються підхідними дробами числа $r$.

Відповідно, окремий $r_k = [a_0; a_1, \dots, a_k] = \frac{p_k}{q_k}$ називається $k$-м підхідним дробом числа $r$.

Приклад

Розглянемо $r = [1; 1, 1, 1, \dots]$. Індукцією можна довести, що $r_k = \frac{F_{k+2}}{F_{k+1}}$, де $F_k$ — послідовність Фібоначчі, визначена як $F_0 = 0$, $F_1 = 1$ і $F_{k} = F_{k-1} + F_{k-2}$. З формули Біне відомо, що

$$r_k = \frac{\phi^{k+2} - \psi^{k+2}}{\phi^{k+1} - \psi^{k+1}},$$

де $\phi = \frac{1+\sqrt{5}}{2} \approx 1.618$ — золотий перетин, а $\psi = \frac{1-\sqrt{5}}{2} = -\frac{1}{\phi} \approx -0.618$. Отже,

$$r = 1+\frac{1}{1+\frac{1}{1+\dots}}=\lim\limits_{k \to \infty} r_k = \phi = \frac{1+\sqrt{5}}{2}.$$

Зауважимо, що в цьому конкретному випадку альтернативним способом знайти $r$ було б розв'язати рівняння

$$r = 1+\frac{1}{r} \implies r^2 = r + 1.$$

Означення

Нехай $r_k = [a_0; a_1, \dots, a_{k-1}, a_k]$. Числа $[a_0; a_1, \dots, a_{k-1}, t]$ для $1 \leq t \leq a_k$ називаються напівпідхідними дробами.

Зазвичай ми називатимемо (напів)підхідні дроби, що більші за $r$, верхніми (напів)підхідними дробами, а ті, що менші за $r$, — нижніми (напів)підхідними дробами.

Означення

На додаток до підхідних дробів, означимо повні частки як $s_k = [a_k; a_{k+1}, a_{k+2}, \dots]$.

Відповідно, окремий $s_k$ ми називатимемо $k$-ю повною часткою числа $r$.

З наведених вище означень можна зробити висновок, що $s_k \geq 1$ для $k \geq 1$.

Розглядаючи $[a_0; a_1, \dots, a_k]$ як формальний алгебраїчний вираз і дозволяючи довільні дійсні числа замість $a_i$, ми отримуємо

$$r = [a_0; a_1, \dots, a_{k-1}, s_k].$$

Зокрема, $r = [s_0] = s_0$. З іншого боку, ми можемо виразити $s_k$ як

$$s_k = [a_k; s_{k+1}] = a_k + \frac{1}{s_{k+1}},$$

що означає, що ми можемо обчислити $a_k = \lfloor s_k \rfloor$ і $s_{k+1} = (s_k - a_k)^{-1}$ з $s_k$.

Послідовність $a_0, a_1, \dots$ визначена коректно, доки $s_k \neq a_k$, що трапляється лише тоді, коли $r$ — раціональне число.

Отже, представлення ланцюговим дробом однозначно визначене для будь-якого ірраціонального числа $r$.

Реалізація

У фрагментах коду ми здебільшого вважатимемо ланцюгові дроби скінченними.

З $s_k$ перехід до $s_{k+1}$ виглядає так:

$$s_k =\left\lfloor s_k \right\rfloor + \frac{1}{s_{k+1}}.$$

З цього виразу наступна повна частка $s_{k+1}$ отримується як

$$s_{k+1} = \left(s_k-\left\lfloor s_k\right\rfloor\right)^{-1}.$$

Для $s_k=\frac{p}{q}$ це означає, що

$$s_{k+1} = \left(\frac{p}{q}-\left\lfloor \frac{p}{q} \right\rfloor\right)^{-1} = \frac{q}{p-q\cdot \lfloor \frac{p}{q} \rfloor} = \frac{q}{p \bmod q}.$$

Отже, обчислення представлення ланцюговим дробом для $r=\frac{p}{q}$ повторює кроки алгоритму Евкліда для $p$ і $q$.

З цього також випливає, що $\gcd(p_k, q_k) = 1$ для $\frac{p_k}{q_k} = [a_0; a_1, \dots, a_k]$. Отже, підхідні дроби завжди нескоротні.

C++

auto fraction(int p, int q) {
    vector<int> a;
    while(q) {
        a.push_back(p / q);
        tie(p, q) = make_pair(q, p % q);
    }
    return a;
}

Python

def fraction(p, q):
    a = []
    while q:
        a.append(p // q)
        p, q = q, p % q
    return a

TypeScript

function fraction(p: number, q: number): number[] {
  const a: number[] = [];
  while (q) {
    a.push(Math.floor(p / q));
    [p, q] = [q, p % q];
  }
  return a;
}

Go

func fraction(p, q int) []int {
	a := []int{}
	for q != 0 {
		a = append(a, p/q)
		p, q = q, p%q
	}
	return a
}

Ключові результати

Щоб дати певну мотивацію для подальшого вивчення ланцюгових дробів, наведемо зараз кілька ключових фактів.

Рекурентне співвідношення

Для підхідних дробів $r_k = \frac{p_k}{q_k}$ виконується таке рекурентне співвідношення, що дозволяє їх швидко обчислювати:

$$\frac{p_k}{q_k}=\frac{a_k p_{k-1} + p_{k-2}}{a_k q_{k-1} + q_{k-2}},$$

де $\frac{p_{-1}}{q_{-1}}=\frac{1}{0}$ і $\frac{p_{-2}}{q_{-2}}=\frac{0}{1}$.

Відхилення

Відхилення $r_k = \frac{p_k}{q_k}$ від $r$ загалом можна оцінити як

$$\left|\frac{p_k}{q_k}-r\right| \leq \frac{1}{q_k q_{k+1}} \leq \frac{1}{q_k^2}.$$

Помноживши обидві частини на $q_k$, отримуємо альтернативну оцінку:

$$|p_k - q_k r| \leq \frac{1}{q_{k+1}}.$$

З наведеного вище рекурентного співвідношення випливає, що $q_k$ зростає принаймні так само швидко, як числа Фібоначчі.

На малюнку нижче ви можете побачити візуалізацію того, як підхідні дроби $r_k$ наближаються до $r=\frac{1+\sqrt 5}{2}$:

$r=\frac{1+\sqrt 5}{2}$ зображено синьою пунктирною лінією. Непарні підхідні дроби наближаються до нього зверху, а парні — знизу.

Ґратчасті оболонки

Розглянемо опуклі оболонки точок над і під прямою $y=rx$.

Непарні підхідні дроби $(q_k;p_k)$ є вершинами верхньої оболонки, тоді як парні підхідні дроби $(q_k;p_k)$ є вершинами нижньої оболонки.

Усі цілочислові вершини на оболонках отримуються як $(q;p)$ такі, що

$$\frac{p}{q} = \frac{tp_{k-1} + p_{k-2}}{tq_{k-1} + q_{k-2}}$$

для цілого $0 \leq t \leq a_k$. Іншими словами, множина ґратчастих точок на оболонках відповідає множині напівпідхідних дробів.

На малюнку нижче ви можете побачити підхідні дроби та напівпідхідні дроби (проміжні сірі точки) числа $r=\frac{9}{7}$.

Найкращі наближення

Нехай $\frac{p}{q}$ — дріб, що мінімізує $\left|r-\frac{p}{q}\right|$ за умови $q \leq x$ для деякого $x$.

Тоді $\frac{p}{q}$ є напівпідхідним дробом числа $r$.

Останній факт дозволяє знаходити найкращі раціональні наближення $r$, перевіряючи його напівпідхідні дроби.

Нижче ви знайдете подальше пояснення, а також трохи інтуїції та інтерпретації цих фактів.

Підхідні дроби

Розгляньмо детальніше підхідні дроби, означені раніше. Для $r=[a_0, a_1, a_2, \dots]$ його підхідними дробами є

\begin{gather} r_0=[a_0],\r_1=[a_0, a_1],\ \dots,\ r_k=[a_0, a_1, \dots, a_k]. \end{gather}

Підхідні дроби — основне поняття ланцюгових дробів, тож важливо вивчити їхні властивості.

Для числа $r$ його $k$-й підхідний дріб $r_k = \frac{p_k}{q_k}$ можна обчислити як

$$r_k = \frac{P_k(a_0,a_1,\dots,a_k)}{P_{k-1}(a_1,\dots,a_k)} = \frac{a_k p_{k-1} + p_{k-2}}{a_k q_{k-1} + q_{k-2}},$$

де $P_k(a_0,\dots,a_k)$ — континуанта, багатовимірний многочлен, означений як

$$P_k(x_0,x_1,\dots,x_k) = \det \begin{bmatrix} x_k & 1 & 0 & \dots & 0 \\ -1 & x_{k-1} & 1 & \dots & 0 \\ 0 & -1 & x_2 & . & \vdots \\ \vdots & \vdots & . & \ddots & 1 \\ 0 & 0 & \dots & -1 & x_0 \end{bmatrix}_{\textstyle .}$$

Отже, $r_k$ є зваженим медіантом дробів $r_{k-1}$ і $r_{k-2}$.

Для узгодженості означають два додаткові підхідні дроби $r_{-1} = \frac{1}{0}$ і $r_{-2} = \frac{0}{1}$.

Детальне пояснення

Чисельник і знаменник $r_k$ можна розглядати як багатовимірні многочлени від $a_0, a_1, \dots, a_k$:

$$r_k = \frac{P_k(a_0, a_1, \dots, a_k)}{Q_k(a_0,a_1, \dots, a_k)}.$$

З означення підхідних дробів,

$$r_k = a_0 + \frac{1}{[a_1;a_2,\dots, a_k]}= a_0 + \frac{Q_{k-1}(a_1, \dots, a_k)}{P_{k-1}(a_1, \dots, a_k)} = \frac{a_0 P_{k-1}(a_1, \dots, a_k) + Q_{k-1}(a_1, \dots, a_k)}{P_{k-1}(a_1, \dots, a_k)}.$$

Звідси випливає $Q_k(a_0, \dots, a_k) = P_{k-1}(a_1, \dots, a_k)$. Це дає співвідношення

$$P_k(a_0, \dots, a_k) = a_0 P_{k-1}(a_1, \dots, a_k) + P_{k-2}(a_2, \dots, a_k).$$

Спочатку $r_0 = \frac{a_0}{1}$ і $r_1 = \frac{a_0 a_1 + 1}{a_1}$, тож

$$\begin{align}P_0(a_0)&=a_0,\\ P_1(a_0, a_1) &= a_0 a_1 + 1.\end{align}$$

Для узгодженості зручно означити $P_{-1} = 1$ і $P_{-2}=0$ та формально вважати, що $r_{-1} = \frac{1}{0}$ і $r_{-2}=\frac{0}{1}$.

З чисельного аналізу відомо, що визначник довільної тридіагональної матриці

$$T_k = \det \begin{bmatrix} a_0 & b_0 & 0 & \dots & 0 \\ c_0 & a_1 & b_1 & \dots & 0 \\ 0 & c_1 & a_2 & . & \vdots \\ \vdots & \vdots & . & \ddots & c_{k-1} \\ 0 & 0 & \dots & b_{k-1} & a_k \end{bmatrix}$$

можна обчислити рекурсивно як $T_k = a_k T_{k-1} - b_{k-1} c_{k-1} T_{k-2}$. Порівнюючи його з $P_k$, отримуємо прямий вираз

$$P_k = \det \begin{bmatrix} x_k & 1 & 0 & \dots & 0 \\ -1 & x_{k-1} & 1 & \dots & 0 \\ 0 & -1 & x_2 & . & \vdots \\ \vdots & \vdots & . & \ddots & 1 \\ 0 & 0 & \dots & -1 & x_0 \end{bmatrix}_{\textstyle .}$$

Цей многочлен також відомий як континуанта через його тісний зв'язок із ланцюговим дробом. Континуанта не зміниться, якщо послідовність на головній діагоналі обернути. Це дає альтернативну формулу для її обчислення:

$$P_k(a_0, \dots, a_k) = a_k P_{k-1}(a_0, \dots, a_{k-1}) + P_{k-2}(a_0, \dots, a_{k-2}).$$

Реалізація

Ми обчислюватимемо підхідні дроби як пару послідовностей $p_{-2}, p_{-1}, p_0, p_1, \dots, p_k$ і $q_{-2}, q_{-1}, q_0, q_1, \dots, q_k$:

C++

auto convergents(vector<int> a) {
    vector<int> p = {0, 1};
    vector<int> q = {1, 0};
    for(auto it: a) {
        p.push_back(p[p.size() - 1] * it + p[p.size() - 2]);
        q.push_back(q[q.size() - 1] * it + q[q.size() - 2]);
    }
    return make_pair(p, q);
}

Python

def convergents(a):
    p = [0, 1]
    q = [1, 0]
    for it in a:
        p.append(p[-1]*it + p[-2])
        q.append(q[-1]*it + q[-2])
    return p, q

TypeScript

function convergents(a: number[]): [number[], number[]] {
  const p: number[] = [0, 1];
  const q: number[] = [1, 0];
  for (const it of a) {
    p.push(p[p.length - 1] * it + p[p.length - 2]);
    q.push(q[q.length - 1] * it + q[q.length - 2]);
  }
  return [p, q];
}

Go

func convergents(a []int) ([]int, []int) {
	p := []int{0, 1}
	q := []int{1, 0}
	for _, it := range a {
		p = append(p, p[len(p)-1]*it+p[len(p)-2])
		q = append(q, q[len(q)-1]*it+q[len(q)-2])
	}
	return p, q
}

Дерева ланцюгових дробів

Існує два основні способи об'єднати всі можливі ланцюгові дроби в корисні деревоподібні структури.

Дерево Штерна–Броко

Дерево Штерна–Броко — це двійкове дерево пошуку, що містить усі різні додатні раціональні числа.

Дерево загалом виглядає так:

Зображення від Aaron Rotenberg ліцензовано під CC BY-SA 3.0

Дроби $\frac{0}{1}$ і $\frac{1}{0}$ "віртуально" зберігаються відповідно зліва і справа дерева.

Тоді дріб у вузлі є медіантом $\frac{a+c}{b+d}$ двох дробів $\frac{a}{b}$ і $\frac{c}{d}$ над ним.

Рекурентне співвідношення $\frac{p_k}{q_k}=\frac{a_k p_{k-1} + p_{k-2}}{a_k q_{k-1} + q_{k-2}}$ означає, що представлення ланцюговим дробом кодує шлях до $\frac{p_k}{q_k}$ у дереві. Щоб знайти $[a_0; a_1, \dots, a_{k}, 1]$, треба зробити $a_0$ кроків праворуч, $a_1$ кроків ліворуч, $a_2$ кроків праворуч і так далі аж до $a_k$.

Батьком $[a_0; a_1, \dots, a_k,1]$ тоді є дріб, отриманий кроком назад у напрямку, що використовувався останнім.

Іншими словами, це $[a_0; a_1, \dots, a_k-1,1]$ коли $a_k > 1$ і $[a_0; a_1, \dots, a_{k-1}, 1]$ коли $a_k = 1$.

Отже, дітьми $[a_0; a_1, \dots, a_k, 1]$ є $[a_0; a_1, \dots, a_k+1, 1]$ і $[a_0; a_1, \dots, a_k, 1, 1]$.

Проіндексуймо дерево Штерна–Броко. Кореневій вершині присвоюється індекс $1$. Тоді для вершини $v$ індекс її лівої дитини присвоюється зміною провідного біта $v$ з $1$ на $10$, а для правої дитини він присвоюється зміною провідного біта з $1$ на $11$:

При такому індексуванні представлення раціонального числа ланцюговим дробом задає кодування довжин серій його двійкового індексу.

Для $\frac{5}{2} = [2;2] = [2;1,1]$ його індекс дорівнює $1011_2$, а його кодування довжин серій, якщо розглядати біти у порядку зростання, дорівнює $[2;1,1]$.

Інший приклад — $\frac{2}{5} = [0;2,2]=[0;2,1,1]$, який має індекс $1100_2$, а його кодування довжин серій справді дорівнює $[0;2,2]$.

Варто зазначити, що дерево Штерна–Броко насправді є декартовим деревом. Тобто це двійкове дерево пошуку за $\frac{p}{q}$, але це купа і за $p$, і за $q$.

Порівняння ланцюгових дробів

Вам дано $A=[a_0; a_1, \dots, a_n]$ і $B=[b_0; b_1, \dots, b_m]$. Який дріб менший?

Розв'язок

Припустимо поки що, що $A$ і $B$ ірраціональні, а їхні представлення ланцюговими дробами задають нескінченний спуск у дереві Штерна–Броко.

Як ми вже згадували, у цьому представленні $a_0$ позначає кількість поворотів праворуч у спуску, $a_1$ позначає кількість послідовних поворотів ліворуч і так далі. Тому, коли ми порівнюємо $a_k$ і $b_k$, якщо $a_k = b_k$, ми просто переходимо до порівняння $a_{k+1}$ і $b_{k+1}$. Інакше, якщо ми на правих спусках, нам слід перевірити, чи $a_k < b_k$, а якщо ми на лівих спусках, нам слід перевірити, чи $a_k > b_k$, щоб визначити, чи $A < B$.

Іншими словами, для ірраціональних $A$ і $B$ буде $A < B$ тоді й лише тоді, коли $(a_0, -a_1, a_2, -a_3, \dots) < (b_0, -b_1, b_2, -b_3, \dots)$ при лексикографічному порівнянні.

Тепер, формально використовуючи $\infty$ як елемент представлення ланцюговим дробом, можна емулювати ірраціональні числа $A-\varepsilon$ і $A+\varepsilon$, тобто елементи, які менші (більші) за $A$, але більші (менші) за будь-яке інше дійсне число. Зокрема, для $A=[a_0; a_1, \dots, a_n]$ один із цих двох елементів можна емулювати як $[a_0; a_1, \dots, a_n, \infty]$, а інший — як $[a_0; a_1, \dots, a_n - 1, 1, \infty]$.

Який із них відповідає $A-\varepsilon$, а який — $A+\varepsilon$, можна визначити за парністю $n$ або порівнявши їх як ірраціональні числа.

Python

# перевіряємо, чи a < b, припускаючи, що a[-1] = b[-1] = infty і a != b
def less(a, b):
    a = [(-1)**i*a[i] for i in range(len(a))]
    b = [(-1)**i*b[i] for i in range(len(b))]
    return a < b

# [a0; a1, ..., ak] -> [a0, a1, ..., ak-1, 1]
def expand(a):
    if a: # порожнє a = inf
        a[-1] -= 1
        a.append(1)
    return a

# повертає a-eps, a+eps
def pm_eps(a):
    b = expand(a.copy())
    a.append(float('inf'))
    b.append(float('inf'))
    return (a, b) if less(a, b) else (b, a)

Найкраща внутрішня точка

Вам дано $\frac{0}{1} \leq \frac{p_0}{q_0} < \frac{p_1}{q_1} \leq \frac{1}{0}$. Знайдіть раціональне число $\frac{p}{q}$ таке, що $(q; p)$ є лексикографічно найменшим і $\frac{p_0}{q_0} < \frac{p}{q} < \frac{p_1}{q_1}$.

Розв'язок

У термінах дерева Штерна–Броко це означає, що нам потрібно знайти LCA дробів $\frac{p_0}{q_0}$ і $\frac{p_1}{q_1}$. Завдяки зв'язку між деревом Штерна–Броко і ланцюговим дробом цей LCA приблизно відповідатиме найбільшому спільному префіксу представлень ланцюговими дробами для $\frac{p_0}{q_0}$ і $\frac{p_1}{q_1}$.

Отже, якщо $\frac{p_0}{q_0} = [a_0; a_1, \dots, a_{k-1}, a_k, \dots]$ і $\frac{p_1}{q_1} = [a_0; a_1, \dots, a_{k-1}, b_k, \dots]$ — ірраціональні числа, то LCA дорівнює $[a_0; a_1, \dots, \min(a_k, b_k)+1]$.

Для раціональних $r_0$ і $r_1$ один із них може бути самим LCA, що змусило б нас розбирати випадки. Щоб спростити розв'язок для раціональних $r_0$ і $r_1$, можна використати представлення ланцюговими дробами чисел $r_0 + \varepsilon$ і $r_1 - \varepsilon$, яке було виведене в попередній задачі.

Python

# знаходить лексикографічно найменше (q, p)
# таке, що p0/q0 < p/q < p1/q1
def middle(p0, q0, p1, q1):
    a0 = pm_eps(fraction(p0, q0))[1]
    a1 = pm_eps(fraction(p1, q1))[0]
    a = []
    for i in range(min(len(a0), len(a1))):
        a.append(min(a0[i], a1[i]))
        if a0[i] != a1[i]:
            break
    a[-1] += 1
    p, q = convergents(a)
    return p[-1], q[-1]

інформація

GCJ 2019, Round 2 - New Elements: Part 2

Вам дано $N$ пар додатних цілих чисел $(C_i, J_i)$. Потрібно знайти пару додатних цілих чисел $(x, y)$ таку, що $C_i x + J_i y$ є строго зростаючою послідовністю.

Серед таких пар знайдіть лексикографічно мінімальну.

Розв'язок

Переформулюємо умову: $A_i x + B_i y$ має бути додатним для всіх $i$, де $A_i = C_i - C_{i-1}$ і $B_i = J_i - J_{i-1}$.

Серед таких рівнянь маємо чотири значущі групи для $A_i x + B_i y > 0$:

1. $A_i, B_i > 0$ можна ігнорувати, оскільки ми шукаємо $x, y > 0$.
2. $A_i, B_i \leq 0$ давало б "IMPOSSIBLE" як відповідь.
3. $A_i > 0$, $B_i \leq 0$. Такі обмеження еквівалентні $\frac{y}{x} < \frac{A_i}{-B_i}$.
4. $A_i \leq 0$, $B_i > 0$. Такі обмеження еквівалентні $\frac{y}{x} > \frac{-A_i}{B_i}$.

Нехай $\frac{p_0}{q_0}$ — найбільший $\frac{-A_i}{B_i}$ з четвертої групи, а $\frac{p_1}{q_1}$ — найменший $\frac{A_i}{-B_i}$ з третьої групи.

Тепер задача така: за даними $\frac{p_0}{q_0} < \frac{p_1}{q_1}$ знайти дріб $\frac{p}{q}$ такий, що $(q;p)$ лексикографічно найменший і $\frac{p_0}{q_0} < \frac{p}{q} < \frac{p_1}{q_1}$.

Python

    def solve():
    n = int(input())
    C = [0] * n
    J = [0] * n
    # p0/q0 < y/x < p1/q1
    p0, q0 = 0, 1
    p1, q1 = 1, 0
    fail = False
    for i in range(n):
        C[i], J[i] = map(int, input().split())
        if i > 0:
            A = C[i] - C[i-1]
            B = J[i] - J[i-1]
            if A <= 0 and B <= 0:
                fail = True
            elif B > 0 and A < 0: # y/x > (-A)/B if B > 0
                if (-A)*q0 > p0*B:
                    p0, q0 = -A, B
            elif B < 0 and A > 0: # y/x < A/(-B) if B < 0
                if A*q1 < p1*(-B):
                    p1, q1 = A, -B
    if p0*q1 >= p1*q0 or fail:
        return 'IMPOSSIBLE'

    p, q = middle(p0, q0, p1, q1)
    return str(q) + ' ' + str(p)

Дерево Калкіна–Вілфа

Дещо простіший спосіб організувати ланцюгові дроби в двійкове дерево — це дерево Калкіна–Вілфа.

Дерево загалом виглядає так:

Зображення від Olli Niemitalo, Proz ліцензовано під CC0 1.0

У корені дерева розташоване число $\frac{1}{1}$. Тоді для вершини з числом $\frac{p}{q}$ її дітьми є $\frac{p}{p+q}$ і $\frac{p+q}{q}$.

На відміну від дерева Штерна–Броко, дерево Калкіна–Вілфа не є двійковим деревом пошуку, тож його не можна використовувати для виконання раціонального бінарного пошуку.

У дереві Калкіна–Вілфа безпосереднім батьком дробу $\frac{p}{q}$ є $\frac{p-q}{q}$ коли $p>q$ і $\frac{p}{q-p}$ в іншому випадку.

Для дерева Штерна–Броко ми використовували рекурентне співвідношення для підхідних дробів. Щоб провести зв'язок між ланцюговим дробом і деревом Калкіна–Вілфа, нам слід пригадати рекурентне співвідношення для повних часток. Якщо $s_k = \frac{p}{q}$, то $s_{k+1} = \frac{q}{p \mod q} = \frac{q}{p-\lfloor p/q \rfloor \cdot q}$.

З іншого боку, якщо ми багаторазово переходимо від $s_k = \frac{p}{q}$ до його батька в дереві Калкіна–Вілфа коли $p > q$, ми опинимося в $\frac{p \mod q}{q} = \frac{1}{s_{k+1}}$. Якщо продовжувати так робити, ми опинимося в $s_{k+2}$, потім $\frac{1}{s_{k+3}}$ і так далі. Звідси можемо вивести, що:

1. Коли $a_0> 0$, безпосереднім батьком $[a_0; a_1, \dots, a_k]$ у дереві Калкіна–Вілфа є $\frac{p-q}{q}=[a_0 - 1; a_1, \dots, a_k]$.
2. Коли $a_0 = 0$ і $a_1 > 1$, його безпосереднім батьком є $\frac{p}{q-p} = [0; a_1 - 1, a_2, \dots, a_k]$.
3. А коли $a_0 = 0$ і $a_1 = 1$, його безпосереднім батьком є $\frac{p}{q-p} = [a_2; a_3, \dots, a_k]$.

Відповідно, дітьми $\frac{p}{q} = [a_0; a_1, \dots, a_k]$ є

1. $\frac{p+q}{q}=1+\frac{p}{q}$, що є $[a_0+1; a_1, \dots, a_k]$,
2. $\frac{p}{p+q} = \frac{1}{1+\frac{q}{p}}$, що є $[0, 1, a_0, a_1, \dots, a_k]$ для $a_0 > 0$ і $[0, a_1+1, a_2, \dots, a_k]$ для $a_0=0$.

Варто зауважити, що якщо ми пронумеруємо вершини дерева Калкіна–Вілфа в порядку пошуку в ширину (тобто корінь має номер $1$, а діти вершини $v$ мають індекси $2v$ і $2v+1$ відповідно), то індекс раціонального числа в дереві Калкіна–Вілфа буде таким самим, як у дереві Штерна–Броко.

Отже, числа на однакових рівнях дерева Штерна–Броко і дерева Калкіна–Вілфа однакові, але їхній порядок різниться через перестановку з обертанням бітів.

Збіжність

Для числа $r$ і його $k$-го підхідного дробу $r_k=\frac{p_k}{q_k}$ виконується така формула:

$$r_k = a_0 + \sum\limits_{i=1}^k \frac{(-1)^{i-1}}{q_i q_{i-1}}.$$

Зокрема, це означає, що

$$r_k - r_{k-1} = \frac{(-1)^{k-1}}{q_k q_{k-1}}$$

і

$$p_k q_{k-1} - p_{k-1} q_k = (-1)^{k-1}.$$

Звідси можемо зробити висновок, що

$$\left| r-\frac{p_k}{q_k} \right| \leq \frac{1}{q_{k+1}q_k} \leq \frac{1}{q_k^2}.$$

Остання нерівність зумовлена тим, що $r_k$ і $r_{k+1}$ загалом розташовані по різні боки від $r$, тож

$$|r-r_k| = |r_k-r_{k+1}|-|r-r_{k+1}| \leq |r_k - r_{k+1}|.$$

Детальне пояснення

Щоб оцінити $|r-r_k|$, почнемо з оцінки різниці між сусідніми підхідними дробами. За означенням,

$$\frac{p_k}{q_k} - \frac{p_{k-1}}{q_{k-1}} = \frac{p_k q_{k-1} - p_{k-1} q_k}{q_k q_{k-1}}.$$

Замінивши $p_k$ і $q_k$ у чисельнику їхніми рекурентними співвідношеннями, отримуємо

$$\begin{align} p_k q_{k-1} - p_{k-1} q_k &= (a_k p_{k-1} + p_{k-2}) q_{k-1} - p_{k-1} (a_k q_{k-1} + q_{k-2}) \\&= p_{k-2} q_{k-1} - p_{k-1} q_{k-2},\end{align}$$

тож чисельник $r_k - r_{k-1}$ завжди є взятим зі знаком мінус чисельником $r_{k-1} - r_{k-2}$. Він, своєю чергою, дорівнює $1$ для

$$r_1 - r_0=\left(a_0+\frac{1}{a_1}\right)-a_0=\frac{1}{a_1},$$

тож

$$r_k - r_{k-1} = \frac{(-1)^{k-1}}{q_k q_{k-1}}.$$

Це дає альтернативне представлення $r_k$ як часткової суми нескінченного ряду:

$$r_k = (r_k - r_{k-1}) + \dots + (r_1 - r_0) + r_0 = a_0 + \sum\limits_{i=1}^k \frac{(-1)^{i-1}}{q_i q_{i-1}}.$$

З рекурентного співвідношення випливає, що $q_k$ монотонно зростає принаймні так само швидко, як числа Фібоначчі, тож

$$r = \lim\limits_{k \to \infty} r_k = a_0 + \sum\limits_{i=1}^\infty \frac{(-1)^{i-1}}{q_i q_{i-1}}$$

завжди визначене коректно, оскільки відповідний ряд завжди збігається. Варто зауважити, що залишковий ряд

$$r-r_k = \sum\limits_{i=k+1}^\infty \frac{(-1)^{i-1}}{q_i q_{i-1}}$$

має той самий знак, що й $(-1)^k$, через те, наскільки швидко спадає $q_i q_{i-1}$. Отже, $r_k$ з парними індексами наближаються до $r$ знизу, тоді як $r_k$ з непарними індексами наближаються до нього зверху:

Підхідні дроби $r=\phi = \frac{1+\sqrt{5}}{2}=[1;1,1,\dots]$ та їхня відстань від $r$.

З цього малюнка ми бачимо, що

$$|r-r_k| = |r_k - r_{k+1}| - |r-r_{k+1}| \leq |r_k - r_{k+1}|,$$

тож відстань між $r$ і $r_k$ ніколи не більша за відстань між $r_k$ і $r_{k+1}$:

$$\left|r-\frac{p_k}{q_k}\right| \leq \frac{1}{q_k q_{k+1}} \leq \frac{1}{q_k^2}.$$

Розширений Евклід?

Вам дано $A, B, C \in \mathbb Z$. Знайдіть $x, y \in \mathbb Z$ такі, що $Ax + By = C$.

Розв'язок

Хоча цю задачу зазвичай розв'язують розширеним алгоритмом Евкліда, існує простий і прямолінійний розв'язок із ланцюговими дробами.

Нехай $\frac{A}{B}=[a_0; a_1, \dots, a_k]$. Вище було доведено, що $p_k q_{k-1} - p_{k-1} q_k = (-1)^{k-1}$. Підставивши $p_k$ і $q_k$ замість $A$ і $B$, отримуємо

$$Aq_{k-1} - Bp_{k-1} = (-1)^{k-1} g,$$

де $g = \gcd(A, B)$. Якщо $C$ ділиться на $g$, то розв'язком є $x = (-1)^{k-1}\frac{C}{g} q_{k-1}$ і $y = (-1)^{k}\frac{C}{g} p_{k-1}$.

Python

# повертає (x, y) таке, що Ax+By=C
# припускає, що таке (x, y) існує
def dio(A, B, C):
    p, q = convergents(fraction(A, B))
    C //= A // p[-1] # ділимо на gcd(A, B)
    t = (-1) if len(p) % 2 else 1
    return t*C*q[-2], -t*C*p[-2]

Дробово-лінійні перетворення

Ще одне важливе поняття для ланцюгових дробів — це так звані дробово-лінійні перетворення.

Означення

Дробово-лінійне перетворення — це функція $f : \mathbb R \to \mathbb R$ така, що $f(x) = \frac{ax+b}{cx+d}$ для деяких $a,b,c,d \in \mathbb R$.

Композиція $(L_0 \circ L_1)(x) = L_0(L_1(x))$ дробово-лінійних перетворень $L_0(x)=\frac{a_0 x + b_0}{c_0 x + d_0}$ і $L_1(x)=\frac{a_1 x + b_1}{c_1 x + d_1}$ сама є дробово-лінійним перетворенням:

$$\frac{a_0\frac{a_1 x + b_1}{c_1 x + d_1} + b_0}{c_0 \frac{a_1 x + b_1}{c_1 x + d_1} + d_0} = \frac{a_0(a_1 x + b_1) + b_0 (c_1 x + d_1)}{c_0 (a_1 x + b_1) + d_0 (c_1 x + d_1)} = \frac{(a_0 a_1 + b_0 c_1) x + (a_0 b_1 + b_0 d_1)}{(c_0 a_1 + d_0 c_1) x + (c_0 b_1 + d_0 d_1)}.$$

Обернене до дробово-лінійного перетворення також є дробово-лінійним перетворенням:

$$y = \frac{ax+b}{cx+d} \iff y(cx+d) = ax + b \iff x = -\frac{dy-b}{cy-a}.$$

інформація

DMOPC '19 Contest 7 P4 - Bob and Continued Fractions

Вам дано масив додатних цілих чисел $a_1, \dots, a_n$. Потрібно відповісти на $m$ запитів. Кожен запит — обчислити $[a_l; a_{l+1}, \dots, a_r]$.

Розв'язок

Ми можемо розв'язати цю задачу за допомогою дерева відрізків, якщо вміємо конкатенувати ланцюгові дроби.

Загалом справедливо, що $[a_0; a_1, \dots, a_k, b_0, b_1, \dots, b_k] = [a_0; a_1, \dots, a_k, [b_1; b_2, \dots, b_k]]$.

Позначимо $L_{k}(x) = [a_k; x] = a_k + \frac{1}{x} = \frac{a_k\cdot x+1}{1\cdot x + 0}$. Зауважимо, що $L_k(\infty) = a_k$. У цих позначеннях виконується

$$[a_0; a_1, \dots, a_k, x] = [a_0; [a_1; [\dots; [a_k; x]]]] = (L_0 \circ L_1 \circ \dots \circ L_k)(x) = \frac{p_k x + p_{k-1}}{q_k x + q_{k-1}}.$$

Отже, задача зводиться до обчислення

$$(L_l \circ L_{l+1} \circ \dots \circ L_r)(\infty).$$

Композиція перетворень асоціативна, тож у кожному вузлі дерева відрізків можна обчислити композицію перетворень у його піддереві.

Дробово-лінійне перетворення ланцюгового дробу

Нехай $L(x) = \frac{ax+b}{cx+d}$. Обчисліть представлення ланцюговим дробом $[b_0; b_1, \dots, b_m]$ числа $L(A)$ для $A=[a_0; a_1, \dots, a_n]$.

Це дозволяє обчислювати $A + \frac{p}{q} = \frac{qA + p}{q}$ і $A \cdot \frac{p}{q} = \frac{p A}{q}$ для будь-якого $\frac{p}{q}$.

Розв'язок

Як ми зазначили вище, $[a_0; a_1, \dots, a_k] = (L_{a_0} \circ L_{a_1} \circ \dots \circ L_{a_k})(\infty)$, тож $L([a_0; a_1, \dots, a_k]) = (L \circ L_{a_0} \circ L_{a_1} \circ \dots L_{a_k})(\infty)$.

Отже, послідовно додаючи $L_{a_0}$, $L_{a_1}$ і так далі, ми зможемо обчислити

$$(L \circ L_{a_0} \circ \dots \circ L_{a_k})(x) = L\left(\frac{p_k x + p_{k-1}}{q_k x + q_{k-1}}\right)=\frac{a_k x + b_k}{c_k x + d_k}.$$

Оскільки $L(x)$ оборотна, вона також монотонна за $x$. Тому для будь-якого $x \geq 0$ виконується, що $L(\frac{p_k x + p_{k-1}}{q_k x + q_{k-1}})$ лежить між $L(\frac{p_k}{q_k}) = \frac{a_k}{c_k}$ і $L(\frac{p_{k-1}}{q_{k-1}}) = \frac{b_k}{d_k}$.

Понад те, для $x=[a_{k+1}; \dots, a_n]$ воно дорівнює $L(A)$. Отже, $b_0 = \lfloor L(A) \rfloor$ лежить між $\lfloor L(\frac{p_k}{q_k}) \rfloor$ і $\lfloor L(\frac{p_{k-1}}{q_{k-1}}) \rfloor$. Коли вони рівні, вони також рівні $b_0$.

Зауважимо, що $L(A) = (L_{b_0} \circ L_{b_1} \circ \dots \circ L_{b_m})(\infty)$. Знаючи $b_0$, ми можемо скомпонувати $L_{b_0}^{-1}$ з поточним перетворенням і продовжувати додавати $L_{a_{k+1}}$, $L_{a_{k+2}}$ і так далі, шукаючи нові заокруглення вниз, які збігатимуться, з яких ми зможемо вивести $b_1$ і так далі, доки не відновимо всі значення $[b_0; b_1, \dots, b_m]$.

Арифметика ланцюгових дробів

Нехай $A=[a_0; a_1, \dots, a_n]$ і $B=[b_0; b_1, \dots, b_m]$. Обчисліть представлення ланцюговими дробами чисел $A+B$ і $A \cdot B$.

Розв'язок

Ідея тут схожа на попередню задачу, але замість $L(x) = \frac{ax+b}{cx+d}$ слід розглянути білінійне дробове перетворення $L(x, y) = \frac{axy+bx+cy+d}{exy+fx+gy+h}$.

Замість $L(x) \mapsto L(L_{a_k}(x))$ ви змінюватимете поточне перетворення як $L(x, y) \mapsto L(L_{a_k}(x), y)$ або $L(x, y) \mapsto L(x, L_{b_k}(y))$.

Потім ви перевіряєте, чи $\lfloor \frac{a}{e} \rfloor = \lfloor \frac{b}{f} \rfloor = \lfloor \frac{c}{g} \rfloor = \lfloor \frac{d}{h} \rfloor$, і якщо вони всі збігаються, ви використовуєте це значення як $c_k$ у результуючому дробі та змінюєте перетворення як

$$L(x, y) \mapsto \frac{1}{L(x, y) - c_k}.$$

Означення

Ланцюговий дріб $x = [a_0; a_1, \dots]$ називається періодичним, якщо $x = [a_0; a_1, \dots, a_k, x]$ для деякого $k$.

Ланцюговий дріб $x = [a_0; a_1, \dots]$ називається зрештою періодичним, якщо $x = [a_0; a_1, \dots, a_k, y]$, де $y$ періодичний.

Для $x = [1; 1, 1, \dots]$ виконується $x = 1 + \frac{1}{x}$, тож $x^2 = x + 1$. Існує загальний зв'язок між періодичними ланцюговими дробами та квадратними рівняннями. Розглянемо таке рівняння:

$$x = [a_0; a_1, \dots, a_k, x].$$

З одного боку, це рівняння означає, що представлення $x$ ланцюговим дробом періодичне з періодом $k+1$.

З іншого боку, використовуючи формулу для підхідних дробів, це рівняння означає, що

$$x = \frac{p_k x + p_{k-1}}{q_k x + q_{k-1}}.$$

Тобто $x$ є дробово-лінійним перетворенням самого себе. З рівняння випливає, що $x$ є коренем рівняння другого степеня:

$$q_k x^2 + (q_{k-1}-p_k)x - p_{k-1} = 0.$$

Подібне міркування виконується для ланцюгових дробів, що зрештою періодичні, тобто $x = [a_0; a_1, \dots, a_k, y]$ для $y=[b_0; b_1, \dots, b_k, y]$. Справді, з першого рівняння виводимо, що $x = L_0(y)$, а з другого рівняння — що $y = L_1(y)$, де $L_0$ і $L_1$ — дробово-лінійні перетворення. Тому,

$$x = (L_0 \circ L_1)(y) = (L_0 \circ L_1 \circ L_0^{-1})(x).$$

Можна далі довести (і це вперше зробив Лагранж), що для довільного квадратного рівняння $ax^2+bx+c=0$ з цілими коефіцієнтами його розв'язок $x$ є зрештою періодичним ланцюговим дробом.

Квадратична ірраціональність

Знайдіть ланцюговий дріб числа $\alpha = \frac{x+y\sqrt{n}}{z}$, де $x, y, z, n \in \mathbb Z$ і $n > 0$ не є точним квадратом.

Розв'язок

Для $k$-ї повної частки $s_k$ числа загалом виконується

$$\alpha = [a_0; a_1, \dots, a_{k-1}, s_k] = \frac{s_k p_{k-1} + p_{k-2}}{s_k q_{k-1} + q_{k-2}}.$$

Тому,

$$s_k = -\frac{\alpha q_{k-1} - p_{k-1}}{\alpha q_k - p_k} = -\frac{q_{k-1} y \sqrt n + (x q_{k-1} - z p_{k-1})}{q_k y \sqrt n + (xq_k-zp_k)}.$$

Помноживши чисельник і знаменник на $(xq_k - zp_k) - q_k y \sqrt n$, ми позбудемося $\sqrt n$ у знаменнику, тож повні частки матимуть вигляд

$$s_k = \frac{x_k + y_k \sqrt n}{z_k}.$$

Знайдемо $s_{k+1}$, припускаючи, що $s_k$ відоме.

Передусім, $a_k = \lfloor s_k \rfloor = \left\lfloor \frac{x_k + y_k \lfloor \sqrt n \rfloor}{z_k} \right\rfloor$. Тоді,

$$s_{k+1} = \frac{1}{s_k-a_k} = \frac{z_k}{(x_k - z_k a_k) + y_k \sqrt n} = \frac{z_k (x_k - y_k a_k) - y_k z_k \sqrt n}{(x_k - y_k a_k)^2 - y_k^2 n}.$$

Отже, якщо позначити $t_k = x_k - y_k a_k$, то виконуватиметься

\begin{align}x_{k+1} &=& z_k t_k, \ y_{k+1} &=& -y_k z_k, \ z_{k+1} &=& t_k^2 - y_k^2 n.\end{align}

Приємне в такому представленні те, що якщо ми скоротимо $x_{k+1}, y_{k+1}, z_{k+1}$ на їхній найбільший спільний дільник, результат буде унікальним. Тому ми можемо використати його, щоб перевірити, чи поточний стан уже повторювався, а також щоб дізнатися, на якому попередньому індексі був цей стан.

Нижче наведено код для обчислення представлення ланцюговим дробом числа $\alpha = \sqrt n$:

Python

# обчислюємо ланцюговий дріб числа sqrt(n)
def sqrt(n):
    n0 = math.floor(math.sqrt(n))
    x, y, z = 1, 0, 1
    a = []
    def step(x, y, z):
        a.append((x * n0 + y) // z)
        t = y - a[-1]*z
        x, y, z = -z*x, z*t, t**2 - n*x**2
        g = math.gcd(x, math.gcd(y, z))
        return x // g, y // g, z // g

    used = dict()
    for i in range(n):
        used[x, y, z] = i
        x, y, z = step(x, y, z)
        if (x, y, z) in used:
            return a

Використовуючи ту саму функцію step, але інші початкові $x$, $y$ і $z$, можна обчислити його для довільного $\frac{x+y \sqrt{n}}{z}$.

інформація

Tavrida NU Akai Contest - Continued Fraction

Вам дано $x$ і $k$, $x$ не є точним квадратом. Нехай $\sqrt x = [a_0; a_1, \dots]$, знайдіть $\frac{p_k}{q_k}=[a_0; a_1, \dots, a_k]$ для $0 \leq k \leq 10^9$.

Розв'язок

Після обчислення періоду $\sqrt x$ можна обчислити $a_k$ за допомогою бінарного піднесення до степеня дробово-лінійного перетворення, породженого представленням ланцюговим дробом. Щоб знайти результуюче перетворення, ви стискаєте період розміру $T$ в одне перетворення і повторюєте його $\lfloor \frac{k-1}{T}\rfloor$ разів, після чого вручну комбінуєте його з рештою перетворень.

Python

x, k = map(int, input().split())

mod = 10**9+7

# компонуємо (A[0]*x + A[1]) / (A[2]*x + A[3]) і (B[0]*x + B[1]) / (B[2]*x + B[3])
def combine(A, B):
    return [t % mod for t in [A[0]*B[0]+A[1]*B[2], A[0]*B[1]+A[1]*B[3], A[2]*B[0]+A[3]*B[2], A[2]*B[1]+A[3]*B[3]]]

A = [1, 0, 0, 1] # (x + 0) / (0*x + 1) = x

a = sqrt(x)

T = len(a) - 1 # період a

# застосовуємо ak + 1/x = (ak*x+1)/(1x+0) до (Ax + B) / (Cx + D)
for i in reversed(range(1, len(a))):
    A = combine([a[i], 1, 1, 0], A)

def bpow(A, n):
    return [1, 0, 0, 1] if not n else combine(A, bpow(A, n-1)) if n % 2 else bpow(combine(A, A), n // 2)


C = (0, 1, 0, 0) # = 1 / 0
while k % T:
    i = k % T
    C = combine([a[i], 1, 1, 0], C)
    k -= 1

C = combine(bpow(A, k // T), C)
C = combine([a[0], 1, 1, 0], C)
print(str(C[1]) + '/' + str(C[3]))

Геометрична інтерпретація

Нехай $\vec r_k = (q_k;p_k)$ для підхідного дробу $r_k = \frac{p_k}{q_k}$. Тоді виконується таке рекурентне співвідношення:

$$\vec r_k = a_k \vec r_{k-1} + \vec r_{k-2}.$$

Нехай $\vec r = (1;r)$. Тоді кожен вектор $(x;y)$ відповідає числу, що дорівнює його кутовому коефіцієнту $\frac{y}{x}$.

З поняттям псевдоскалярного добутку $(x_1;y_1) \times (x_2;y_2) = x_1 y_2 - x_2 y_1$ можна показати (див. пояснення нижче), що

$$s_k = -\frac{\vec r_{k-2} \times \vec r}{\vec r_{k-1} \times \vec r} = \left|\frac{\vec r_{k-2} \times \vec r}{\vec r_{k-1} \times \vec r}\right|.$$

Остання рівність зумовлена тим, що $r_{k-1}$ і $r_{k-2}$ лежать по різні боки від $r$, тож псевдоскалярні добутки $\vec r_{k-1}$ і $\vec r_{k-2}$ з $\vec r$ мають різні знаки. З огляду на $a_k = \lfloor s_k \rfloor$, формула для $\vec r_k$ тепер виглядає так:

$$\vec r_k = \vec r_{k-2} + \left\lfloor \left| \frac{\vec r \times \vec r_{k-2}}{\vec r \times \vec r_{k-1}}\right|\right\rfloor \vec r_{k-1}.$$

Зауважимо, що $\vec r_k \times r = (q;p) \times (1;r) = qr - p$, тож

$$a_k = \left\lfloor \left| \frac{q_{k-1}r-p_{k-1}}{q_{k-2}r-p_{k-2}} \right| \right\rfloor.$$

Пояснення

Як ми вже зазначали, $a_k = \lfloor s_k \rfloor$, де $s_k = [a_k; a_{k+1}, a_{k+2}, \dots]$. З іншого боку, з рекурентного співвідношення для підхідних дробів виводимо, що

$$r = [a_0; a_1, \dots, a_{k-1}, s_k] = \frac{s_k p_{k-1} + p_{k-2}}{s_k q_{k-1} + q_{k-2}}.$$

У векторній формі це переписується як

$$\vec r \parallel s_k \vec r_{k-1} + \vec r_{k-2},$$

що означає, що $\vec r$ і $s_k \vec r_{k-1} + \vec r_{k-2}$ колінеарні (тобто мають однаковий кутовий коефіцієнт). Узявши псевдоскалярний добуток обох частин з $\vec r$, отримуємо

$$0 = s_k (\vec r_{k-1} \times \vec r) + (\vec r_{k-2} \times \vec r),$$

що дає остаточну формулу

$$s_k = -\frac{\vec r_{k-2} \times \vec r}{\vec r_{k-1} \times \vec r}.$$

Алгоритм витягування носа

Щоразу, коли ви додаєте $\vec r_{k-1}$ до вектора $\vec p$, значення $\vec p \times \vec r$ збільшується на $\vec r_{k-1} \times \vec r$.

Отже, $a_k=\lfloor s_k \rfloor$ — це максимальна ціла кількість векторів $\vec r_{k-1}$, які можна додати до $\vec r_{k-2}$ без зміни знаку векторного добутку з $\vec r$.

Іншими словами, $a_k$ — це максимальна ціла кількість разів, скільки ви можете додати $\vec r_{k-1}$ до $\vec r_{k-2}$, не перетинаючи пряму, задану $\vec r$:

Підхідні дроби $r=\frac{7}{9}=[0;1,3,2]$. Напівпідхідні дроби відповідають проміжним точкам між сірими стрілками.

На малюнку вище $\vec r_2 = (4;3)$ отримується багаторазовим додаванням $\vec r_1 = (1;1)$ до $\vec r_0 = (1;0)$.

Коли вже неможливо далі додавати $\vec r_1$ до $\vec r_0$ без перетину прямої $y=rx$, ми переходимо на інший бік і багаторазово додаємо $\vec r_2$ до $\vec r_1$, щоб отримати $\vec r_3 = (9;7)$.

Ця процедура породжує експоненційно довші вектори, що наближаються до прямої.

За цю властивість процедуру породження послідовних векторів підхідних дробів Борис Делоне назвав алгоритмом витягування носа.

Якщо ми поглянемо на трикутник, побудований на точках $\vec r_{k-2}$, $\vec r_{k}$ і $\vec 0$, ми помітимо, що його подвоєна площа дорівнює

$$|\vec r_{k-2} \times \vec r_k| = |\vec r_{k-2} \times (\vec r_{k-2} + a_k \vec r_{k-1})| = a_k |\vec r_{k-2} \times \vec r_{k-1}| = a_k.$$

У поєднанні з теоремою Піка це означає, що немає ґратчастих точок строго всередині трикутника, а єдиними ґратчастими точками на його межі є $\vec 0$ і $\vec r_{k-2} + t \cdot \vec r_{k-1}$ для всіх цілих $t$ таких, що $0 \leq t \leq a_k$. Якщо об'єднати це для всіх можливих $k$, це означає, що немає цілих точок у просторі між многокутниками, утвореними векторами підхідних дробів з парними і непарними індексами.

Це, своєю чергою, означає, що $\vec r_k$ з непарними коефіцієнтами утворюють опуклу оболонку ґратчастих точок з $x \geq 0$ над прямою $y=rx$, тоді як $\vec r_k$ з парними коефіцієнтами утворюють опуклу оболонку ґратчастих точок з $x > 0$ під прямою $y=rx$.

Означення

Ці многокутники також відомі як многокутники Клейна, названі на честь Фелікса Клейна, який першим запропонував цю геометричну інтерпретацію ланцюгових дробів.

Приклади задач

Тепер, коли найважливіші факти та поняття було введено, час заглибитися в конкретні приклади задач.

Опукла оболонка під прямою

Знайдіть опуклу оболонку ґратчастих точок $(x;y)$ таких, що $0 \leq x \leq N$ і $0 \leq y \leq rx$ для $r=[a_0;a_1,\dots,a_k]=\frac{p_k}{q_k}$.

Розв'язок

Якби ми розглядали необмежену множину $0 \leq x$, верхня опукла оболонка задавалася б самою прямою $y=rx$.

Однак з додатковим обмеженням $x \leq N$ нам зрештою довелося б відхилитися від прямої, щоб підтримувати коректну опуклу оболонку.

Нехай $t = \lfloor \frac{N}{q_k}\rfloor$, тоді перші $t$ ґратчастих точок на оболонці після $(0;0)$ — це $\alpha \cdot (q_k; p_k)$ для цілого $1 \leq \alpha \leq t$.

Однак $(t+1)(q_k; p_k)$ не може бути наступною ґратчастою точкою, оскільки $(t+1)q_k$ більше за $N$.

Щоб дістатися до наступних ґратчастих точок на оболонці, нам слід дістатися до точки $(x;y)$, яка відхиляється від $y=rx$ на найменший відступ, зберігаючи при цьому $x \leq N$.

Опукла оболонка ґратчастих точок під $y=\frac{4}{7}x$ для $0 \leq x \leq 19$ складається з точок $(0;0), (7;4), (14;8), (16;9), (18;10), (19;10)$.

Нехай $(x; y)$ — остання поточна точка опуклої оболонки. Тоді наступна точка $(x'; y')$ така, що $x' \leq N$ і $(x'; y') - (x; y) = (\Delta x; \Delta y)$ якомога ближча до прямої $y=rx$. Іншими словами, $(\Delta x; \Delta y)$ максимізує $r \Delta x - \Delta y$ за умов $\Delta x \leq N - x$ і $\Delta y \leq r \Delta x$.

Такі точки лежать на опуклій оболонці ґратчастих точок під $y=rx$. Іншими словами, $(\Delta x; \Delta y)$ має бути нижнім напівпідхідним дробом $r$.

Тобто $(\Delta x; \Delta y)$ має вигляд $(q_{i-1}; p_{i-1}) + t \cdot (q_i; p_i)$ для деякого непарного числа $i$ і $0 \leq t < a_i$.

Щоб знайти такий $i$, ми можемо перебрати всі можливі $i$, починаючи з найбільшого, і використати $t = \lfloor \frac{N-x-q_{i-1}}{q_i} \rfloor$ для $i$ такого, що $N-x-q_{i-1} \geq 0$.

З $(\Delta x; \Delta y) = (q_{i-1}; p_{i-1}) + t \cdot (q_i; p_i)$ умова $\Delta y \leq r \Delta x$ зберігатиметься завдяки властивостям напівпідхідних дробів.

А $t < a_i$ виконуватиметься, тому що ми вже вичерпали напівпідхідні дроби, отримані з $i+2$, тож $x + q_{i-1} + a_i q_i = x+q_{i+1}$ більше за $N$.

Тепер, коли ми можемо додати $(\Delta x; \Delta y)$ до $(x;y)$ $k = \lfloor \frac{N-x}{\Delta x} \rfloor$ разів, перш ніж перевищимо $N$, після чого ми спробуємо наступний напівпідхідний дріб.

C++

// повертає [ah, ph, qh] такі, що точки r[i]=(ph[i], qh[i]) утворюють верхню опуклу оболонку
// ґратчастих точок на 0 <= x <= N і 0 <= y <= r * x, де r = [a0; a1, a2, ...]
// і на відрізку між r[i] та r[i+1] є ah[i]-1 цілих точок
auto hull(auto a, int N) {
    auto [p, q] = convergents(a);
    int t = N / q.back();
    vector ah = {t};
    vector ph = {0, t*p.back()};
    vector qh = {0, t*q.back()};

    for(int i = q.size() - 1; i >= 0; i--) {
        if(i % 2) {
            while(qh.back() + q[i - 1] <= N) {
                t = (N - qh.back() - q[i - 1]) / q[i];
                int dp = p[i - 1] + t * p[i];
                int dq = q[i - 1] + t * q[i];
                int k = (N - qh.back()) / dq;
                ah.push_back(k);
                ph.push_back(ph.back() + k * dp);
                qh.push_back(qh.back() + k * dq);
            }
        }
    }
    return make_tuple(ah, ph, qh);
}

Python

# повертає [ah, ph, qh] такі, що точки r[i]=(ph[i], qh[i]) утворюють верхню опуклу оболонку
# ґратчастих точок на 0 <= x <= N і 0 <= y <= r * x, де r = [a0; a1, a2, ...]
# і на відрізку між r[i] та r[i+1] є ah[i]-1 цілих точок
def hull(a, N):
    p, q = convergents(a)
    t = N // q[-1]
    ah = [t]
    ph = [0, t*p[-1]]
    qh = [0, t*q[-1]]
    for i in reversed(range(len(q))):
        if i % 2 == 1:
            while qh[-1] + q[i-1] <= N:
                t = (N - qh[-1] - q[i-1]) // q[i]
                dp = p[i-1] + t*p[i]
                dq = q[i-1] + t*q[i]
                k = (N - qh[-1]) // dq
                ah.append(k)
                ph.append(ph[-1] + k * dp)
                qh.append(qh[-1] + k * dq)
    return ah, ph, qh

TypeScript

// повертає [ah, ph, qh] такі, що точки r[i]=(ph[i], qh[i]) утворюють верхню опуклу оболонку
// ґратчастих точок на 0 <= x <= N і 0 <= y <= r * x, де r = [a0; a1, a2, ...]
// і на відрізку між r[i] та r[i+1] є ah[i]-1 цілих точок
function hull(a: number[], N: number): [number[], number[], number[]] {
  const [p, q] = convergents(a);
  let t = Math.floor(N / q[q.length - 1]);
  const ah = [t];
  const ph = [0, t * p[p.length - 1]];
  const qh = [0, t * q[q.length - 1]];
  for (let i = q.length - 1; i >= 0; i--) {
    if (i % 2) {
      while (qh[qh.length - 1] + q[i - 1] <= N) {
        t = Math.floor((N - qh[qh.length - 1] - q[i - 1]) / q[i]);
        const dp = p[i - 1] + t * p[i];
        const dq = q[i - 1] + t * q[i];
        const k = Math.floor((N - qh[qh.length - 1]) / dq);
        ah.push(k);
        ph.push(ph[ph.length - 1] + k * dp);
        qh.push(qh[qh.length - 1] + k * dq);
      }
    }
  }
  return [ah, ph, qh];
}

Go

// повертає (ah, ph, qh) такі, що точки r[i]=(ph[i], qh[i]) утворюють верхню опуклу оболонку
// ґратчастих точок на 0 <= x <= N і 0 <= y <= r * x, де r = [a0; a1, a2, ...]
// і на відрізку між r[i] та r[i+1] є ah[i]-1 цілих точок
func hull(a []int, N int) ([]int, []int, []int) {
	p, q := convergents(a)
	t := N / q[len(q)-1]
	ah := []int{t}
	ph := []int{0, t * p[len(p)-1]}
	qh := []int{0, t * q[len(q)-1]}
	for i := len(q) - 1; i >= 0; i-- {
		if i%2 == 1 {
			for qh[len(qh)-1]+q[i-1] <= N {
				t = (N - qh[len(qh)-1] - q[i-1]) / q[i]
				dp := p[i-1] + t*p[i]
				dq := q[i-1] + t*q[i]
				k := (N - qh[len(qh)-1]) / dq
				ah = append(ah, k)
				ph = append(ph, ph[len(ph)-1]+k*dp)
				qh = append(qh, qh[len(qh)-1]+k*dq)
			}
		}
	}
	return ah, ph, qh
}

інформація

Timus - Crime and Punishment

Вам дано цілі числа $A$, $B$ і $N$. Знайдіть $x \geq 0$ і $y \geq 0$ такі, що $Ax + By \leq N$ і $Ax + By$ якомога більше.

Розв'язок

У цій задачі виконується $1 \leq A, B, N \leq 2 \cdot 10^9$, тож її можна розв'язати за $O(\sqrt N)$. Однак існує розв'язок за $O(\log N)$ із ланцюговими дробами.

Для нашої зручності ми обернемо напрямок $x$, зробивши заміну $x \mapsto \lfloor \frac{N}{A}\rfloor - x$, так що тепер нам потрібно знайти точку $(x; y)$ таку, що $0 \leq x \leq \lfloor \frac{N}{A} \rfloor$, $By - Ax \leq N \;\bmod\; A$ і $By - Ax$ якомога більше. Оптимальне $y$ для кожного $x$ має значення $\lfloor \frac{Ax + (N \bmod A)}{B} \rfloor$.

Щоб розглядати це загальніше, ми напишемо функцію, що знаходить найкращу точку на $0 \leq x \leq N$ і $y = \lfloor \frac{Ax+B}{C} \rfloor$.

Основна ідея розв'язку в цій задачі по суті повторює попередню задачу, але замість використання нижніх напівпідхідних дробів для відхилення від прямої ви використовуєте верхні напівпідхідні дроби, щоб наблизитися до прямої, не перетинаючи її та не порушуючи $x \leq N$. На жаль, на відміну від попередньої задачі, вам потрібно переконатися, що ви не перетинаєте пряму $y=\frac{Ax+B}{C}$, наближаючись до неї, тож слід це пам'ятати при обчисленні коефіцієнта напівпідхідного дробу $t$.

Python

# (x, y) таке, що y = (A*x+B) // C,
# Cy - Ax максимальне і 0 <= x <= N.
def closest(A, B, C, N):
    # y <= (A*x + B)/C <=> diff(x, y) <= B
    def diff(x, y):
        return C*y-A*x
    a = fraction(A, C)
    p, q = convergents(a)
    ph = [B // C]
    qh = [0]
    for i in range(2, len(q) - 1):
        if i % 2 == 0:
            while diff(qh[-1] + q[i+1], ph[-1] + p[i+1]) <= B:
                t = 1 + (diff(qh[-1] + q[i-1], ph[-1] + p[i-1]) - B - 1) // abs(diff(q[i], p[i]))
                dp = p[i-1] + t*p[i]
                dq = q[i-1] + t*q[i]
                k = (N - qh[-1]) // dq
                if k == 0:
                    return qh[-1], ph[-1]
                if diff(dq, dp) != 0:
                    k = min(k, (B - diff(qh[-1], ph[-1])) // diff(dq, dp))
                qh.append(qh[-1] + k*dq)
                ph.append(ph[-1] + k*dp)
    return qh[-1], ph[-1]

def solve(A, B, N):
    x, y = closest(A, N % A, B, N // A)
    return N // A - x, y

інформація

June Challenge 2017 - Euler Sum

Обчисліть $\sum\limits_{x=1}^N \lfloor ex \rfloor$, де $e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, \dots, 1, 2n, 1, \dots]$ — число Ейлера і $N \leq 10^{4000}$.

Розв'язок

Ця сума дорівнює кількості ґратчастих точок $(x;y)$ таких, що $1 \leq x \leq N$ і $1 \leq y \leq ex$.

Після побудови опуклої оболонки точок під $y=ex$ цю кількість можна обчислити за допомогою теореми Піка:

C++

// сума floor(k * x) для k з [1, N] і x = [a0; a1, a2, ...]
int sum_floor(auto a, int N) {
    N++;
    auto [ah, ph, qh] = hull(a, N);

    // Кількість ґратчастих точок усередині вертикальної прямокутної трапеції
    // на точках (0; 0) - (0; y1) - (dx; y2) - (dx; 0), що має
    // a+1 цілих точок на відрізку (0; y1) - (dx; y2).
    auto picks = [](int y1, int y2, int dx, int a) {
        int b = y1 + y2 + a + dx;
        int A = (y1 + y2) * dx;
        return (A - b + 2) / 2 + b - (y2 + 1);
    };

    int ans = 0;
    for(size_t i = 1; i < qh.size(); i++) {
        ans += picks(ph[i - 1], ph[i], qh[i] - qh[i - 1], ah[i - 1]);
    }
    return ans - N;
}

Python

# сума floor(k * x) для k з [1, N] і x = [a0; a1, a2, ...]
def sum_floor(a, N):
    N += 1
    ah, ph, qh = hull(a, N)

    # Кількість ґратчастих точок усередині вертикальної прямокутної трапеції
    # на точках (0; 0) - (0; y1) - (dx; y2) - (dx; 0), що має
    # a+1 цілих точок на відрізку (0; y1) - (dx; y2).
    def picks(y1, y2, dx, a):
        b = y1 + y2 + a + dx
        A = (y1 + y2) * dx
        return (A - b + 2) // 2 + b - (y2 + 1)

    ans = 0
    for i in range(1, len(qh)):
        ans += picks(ph[i-1], ph[i], qh[i]-qh[i-1], ah[i-1])
    return ans - N

TypeScript

// сума floor(k * x) для k з [1, N] і x = [a0; a1, a2, ...]
function sum_floor(a: number[], N: number): number {
  N++;
  const [ah, ph, qh] = hull(a, N);

  // Кількість ґратчастих точок усередині вертикальної прямокутної трапеції
  // на точках (0; 0) - (0; y1) - (dx; y2) - (dx; 0), що має
  // a+1 цілих точок на відрізку (0; y1) - (dx; y2).
  const picks = (y1: number, y2: number, dx: number, a: number): number => {
    const b = y1 + y2 + a + dx;
    const A = (y1 + y2) * dx;
    return Math.floor((A - b + 2) / 2) + b - (y2 + 1);
  };

  let ans = 0;
  for (let i = 1; i < qh.length; i++) {
    ans += picks(ph[i - 1], ph[i], qh[i] - qh[i - 1], ah[i - 1]);
  }
  return ans - N;
}

Go

// сума floor(k * x) для k з [1, N] і x = [a0; a1, a2, ...]
func sumFloor(a []int, N int) int {
	N++
	ah, ph, qh := hull(a, N)

	// Кількість ґратчастих точок усередині вертикальної прямокутної трапеції
	// на точках (0; 0) - (0; y1) - (dx; y2) - (dx; 0), що має
	// a+1 цілих точок на відрізку (0; y1) - (dx; y2).
	picks := func(y1, y2, dx, a int) int {
		b := y1 + y2 + a + dx
		A := (y1 + y2) * dx
		return (A-b+2)/2 + b - (y2 + 1)
	}

	ans := 0
	for i := 1; i < len(qh); i++ {
		ans += picks(ph[i-1], ph[i], qh[i]-qh[i-1], ah[i-1])
	}
	return ans - N
}

інформація

NAIPC 2019 - It's a Mod, Mod, Mod, Mod World

За даними $p$, $q$ і $n$ обчисліть $\sum\limits_{i=1}^n [p \cdot i \bmod q]$.

Розв'язок

Ця задача зводиться до попередньої, якщо зауважити, що $a \bmod b = a - \lfloor \frac{a}{b} \rfloor b$. З цим фактом сума зводиться до

$$\sum\limits_{i=1}^n \left(p \cdot i - \left\lfloor \frac{p \cdot i}{q} \right\rfloor q\right) = \frac{pn(n+1)}{2}-q\sum\limits_{i=1}^n \left\lfloor \frac{p \cdot i}{q}\right\rfloor.$$

Однак сумування $\lfloor rx \rfloor$ для $x$ від $1$ до $N$ — це те, що ми вміємо з попередньої задачі.

C++

void solve(int p, int q, int N) {
    cout << p * N * (N + 1) / 2 - q * sum_floor(fraction(p, q), N) << "\n";
}

Python

def solve(p, q, N):
    return p * N * (N + 1) // 2 - q * sum_floor(fraction(p, q), N)

TypeScript

function solve(p: number, q: number, N: number): number {
  return (p * N * (N + 1)) / 2 - q * sum_floor(fraction(p, q), N);
}

Go

func solve(p, q, N int) int {
	return p*N*(N+1)/2 - q*sumFloor(fraction(p, q), N)
}

інформація

Library Checker - Sum of Floor of Linear

За даними $N$, $M$, $A$ і $B$ обчисліть $\sum\limits_{i=0}^{N-1} \lfloor \frac{A \cdot i + B}{M} \rfloor$.

Розв'язок

Це найтехнічніше клопітна задача дотепер.

Можна використати той самий підхід і побудувати повну опуклу оболонку точок під прямою $y = \frac{Ax+B}{M}$.

Ми вже знаємо, як розв'язати це для $B = 0$. Понад те, ми вже знаємо, як побудувати цю опуклу оболонку аж до найближчої до цієї прямої ґратчастої точки на відрізку $[0, N-1]$ (це робиться в задачі "Crime and Punishment" вище).

Тепер слід зауважити, що щойно ми досягли найближчої до прямої точки, ми можемо просто вважати, що пряма насправді проходить через найближчу точку, оскільки немає інших ґратчастих точок на $[0, N-1]$ між справжньою прямою і прямою, зміщеною трохи нижче, щоб проходити через найближчу точку.

Тобто, щоб побудувати повну опуклу оболонку під прямою $y=\frac{Ax+B}{M}$ на $[0, N-1]$, ми можемо побудувати її аж до найближчої до прямої точки на $[0, N-1]$, а потім продовжити так, ніби пряма проходить через цю точку, повторно використовуючи алгоритм побудови опуклої оболонки з $B=0$:

Python

# оболонка ґратчастих (x, y) таких, що C*y <= A*x+B
def hull(A, B, C, N):
    def diff(x, y):
        return C*y-A*x
    a = fraction(A, C)
    p, q = convergents(a)
    ah = []
    ph = [B // C]
    qh = [0]

    def insert(dq, dp):
        k = (N - qh[-1]) // dq
        if diff(dq, dp) > 0:
            k = min(k, (B - diff(qh[-1], ph[-1])) // diff(dq, dp))
        ah.append(k)
        qh.append(qh[-1] + k*dq)
        ph.append(ph[-1] + k*dp)

    for i in range(1, len(q) - 1):
        if i % 2 == 0:
            while diff(qh[-1] + q[i+1], ph[-1] + p[i+1]) <= B:
                t = (B - diff(qh[-1] + q[i+1], ph[-1] + p[i+1])) // abs(diff(q[i], p[i]))
                dp = p[i+1] - t*p[i]
                dq = q[i+1] - t*q[i]
                if dq < 0 or qh[-1] + dq > N:
                    break
                insert(dq, dp)

    insert(q[-1], p[-1])

    for i in reversed(range(len(q))):
        if i % 2 == 1:
            while qh[-1] + q[i-1] <= N:
                t = (N - qh[-1] - q[i-1]) // q[i]
                dp = p[i-1] + t*p[i]
                dq = q[i-1] + t*q[i]
                insert(dq, dp)
    return ah, ph, qh

інформація

OKC 2 - From Modular to Rational

Існує раціональне число $\frac{p}{q}$ таке, що $1 \leq p, q \leq 10^9$. Ви можете запитати значення $p q^{-1}$ за модулем $m \sim 10^9$ для кількох простих чисел $m$. Відновіть $\frac{p}{q}$.

Еквівалентне формулювання: Знайдіть $x$, що дає мінімум $Ax \;\bmod\; M$ для $1 \leq x \leq N$.

Розв'язок

За китайською теоремою про остачі запитування результату за модулем кількох простих чисел те саме, що запитування його за модулем їхнього добутку. Через це без втрати загальності вважатимемо, що ми знаємо остачу за модулем достатньо великого числа $m$.

Може існувати кілька можливих розв'язків $(p, q)$ для $p \equiv qr \pmod m$ за даної остачі $r$. Однак, якщо $(p_1, q_1)$ і $(p_2, q_2)$ обидва є розв'язками, то також виконується $p_1 q_2 \equiv p_2 q_1 \pmod m$. Припускаючи, що $\frac{p_1}{q_1} \neq \frac{p_2}{q_2}$, це означає, що $|p_1 q_2 - p_2 q_1|$ становить принаймні $m$.

В умові нам сказали, що $1 \leq p, q \leq 10^9$, тож якщо і $p_1, q_1$, і $p_2, q_2$ не перевищують $10^9$, то різниця не перевищує $10^{18}$. Для $m > 10^{18}$ це означає, що розв'язок $\frac{p}{q}$ з $1 \leq p, q \leq 10^9$ єдиний як раціональне число.

Отже, задача зводиться до такого: за даним $r$ за модулем $m$ знайти будь-яке $q$ таке, що $1 \leq q \leq 10^9$ і $qr \;\bmod\; m \leq 10^9$.

Це по суті те саме, що знайти $q$, яке дає мінімально можливе $qr \bmod m$ для $1 \leq q \leq 10^9$.

Для $qr = km + b$ це означає, що нам потрібно знайти пару $(q, m)$ таку, що $1 \leq q \leq 10^9$ і $qr - km \geq 0$ мінімально можливе.

Оскільки $m$ стале, ми можемо поділити на нього і далі переформулювати це як: знайти $q$ таке, що $1 \leq q \leq 10^9$ і $\frac{r}{m} q - k \geq 0$ мінімально можливе.

У термінах ланцюгових дробів це означає, що $\frac{k}{q}$ є найкращим діофантовим наближенням до $\frac{r}{m}$, і достатньо перевірити лише нижні напівпідхідні дроби $\frac{r}{m}$.

Python

# знаходимо Q, що мінімізує Q*r mod m для 1 <= k <= n < m 
def mod_min(r, n, m):
    a = fraction(r, m)
    p, q = convergents(a)
    for i in range(2, len(q)):
        if i % 2 == 1 and (i + 1 == len(q) or q[i+1] > n):
            t = (n - q[i-1]) // q[i]
            return q[i-1] + t*q[i]

Задачі для практики

• UVa OJ - Continued Fractions
• ProjectEuler+ #64: Odd period square roots
• Codeforces Round #184 (Div. 2) - Continued Fractions
• Codeforces Round #201 (Div. 1) - Doodle Jump
• Codeforces Round #325 (Div. 1) - Alice, Bob, Oranges and Apples
• POJ Founder Monthly Contest 2008.03.16 - A Modular Arithmetic Challenge
• 2019 Multi-University Training Contest 5 - fraction
• SnackDown 2019 Elimination Round - Election Bait
• Code Jam 2019 round 2 - Continued Fraction

Відеоматеріали