Агуулгыг алгасах

Гинжин бутархай

Гинжин бутархай гэдэг нь бодит тоог рационал тоонуудын тодорхой нэг нийлэх дараалал хэлбэрээр илэрхийлэхийг хэлнэ. Тэдгээрийг тооцоолоход хялбар бөгөөд суурь бодит тооныхоо хамгийн сайн рационал ойролцоололыг (хуваарь нь өгөгдсөн утгаас хэтрэхгүй бүх тооны дундаас) үр ашигтай олоход ашиглаж болдог тул программчлалын тэмцээнд хэрэгтэй байдаг.

Үүнээс гадна гинжин бутархай нь Евклидийн алгоритмтай нягт холбоотой бөгөөд энэ нь түүнийг тооны онолын хэд хэдэн бодлогод ашигтай болгодог.

Гинжин бутархайн илэрхийлэл

Тодорхойлолт

$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]$ гэж тэмдэглэнэ.

Example

$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].$$

Түүнчлэн $r=\frac{p}{q}$-ийн хувьд ийм гинжин бутархайн $k$ урт нь $k = O(\log \min(p, q))$ гэж үнэлэгдэнэ.

Үүний цаад учир шалтгаан нь гинжин бутархайг байгуулах нарийн ширийнийг судлахад тодорхой болно.

Тодорхойлолт

$a_1, a_2, \dots \geq 1$ байх $a_0,a_1,a_2, \dots$ бүхэл тооны дараалал өгөгдсөн байг. $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]$ болохыг анхаарна уу.

Өөр нэг чухал ажиглалт бол $a_0 > 0$ үед $\frac{1}{r}=[0;a_0, a_1, \dots]$, харин $a_0 = 0$ үед $\frac{1}{r} = [a_1; a_2, \dots]$ байдаг явдал юм.

Тодорхойлолт

Дээрх тодорхойлолт дахь $r_0, r_1, r_2, \dots$ рационал тоонуудыг $r$-ийн ойртох бутархай гэж нэрлэнэ.

Үүний дагуу тус бүрийн $r_k = [a_0; a_1, \dots, a_k] = \frac{p_k}{q_k}$-ийг $r$-ийн $k$ дугаар ойртох бутархай гэж нэрлэнэ.

Example

$r = [1; 1, 1, 1, \dots]$ гэж авч үзье. $F_0 = 0$, $F_1 = 1$, $F_{k} = F_{k-1} + F_{k-2}$ гэж тодорхойлогдох Фибоначчийн дараалал $F_k$-ийн хувьд $r_k = \frac{F_{k+2}}{F_{k+1}}$ болохыг индукцээр батлаж болно. Бинений томьёогоор

$$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]$ байг. $1 \leq t \leq a_k$ байх $[a_0; a_1, \dots, a_{k-1}, t]$ тоонуудыг хагас ойртох бутархай гэж нэрлэнэ.

$r$-ээс их (хагас) ойртох бутархайг бид ихэвчлэн дээд (хагас) ойртох бутархай, $r$-ээс бага байгаа тэдгээрийг доод (хагас) ойртох бутархай гэж нэрлэнэ.

Тодорхойлолт

Ойртох бутархайг нөхөх байдлаар бүтэн ноогдвор-ыг $s_k = [a_k; a_{k+1}, a_{k+2}, \dots]$ гэж тодорхойлно.

Үүний дагуу тус бүрийн $s_k$-г $r$-ийн $k$ дугаар бүтэн ноогдвор гэж нэрлэнэ.

Дээрх тодорхойлолтуудаас $k \geq 1$ үед $s_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}},$$

гэж илэрхийлж болох ба энэ нь бид $s_k$-аас $a_k = \lfloor s_k \rfloor$ ба $s_{k+1} = (s_k - a_k)^{-1}$-ийг тооцоолж чадна гэсэн үг.

$a_0, a_1, \dots$ дараалал нь $s_k=a_k$ болохоос бусад тохиолдолд сайн тодорхойлогдох бөгөөд энэ нь зөвхөн $r$ рационал тоо байхад тохиолдоно.

Тиймээс гинжин бутархайн илэрхийлэл нь дурын $r$ иррационал тооны хувьд цор ганцаараа тодорхойлогдоно.

Implementation

In the code snippets we will mostly assume finite continued fractions.

From $s_k$, the transition to $s_{k+1}$ looks like

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

From this expression, the next complete quotient $s_{k+1}$ is obtained as

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

For $s_k=\frac{p}{q}$ it means that

$$ 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}. $$

Thus, the computation of a continued fraction representation for $r=\frac{p}{q}$ follows the steps of the Euclidean algorithm for $p$ and $q$.

From this also follows that $\gcd(p_k, q_k) = 1$ for $\frac{p_k}{q_k} = [a_0; a_1, \dots, a_k]$. Hence, convergents are always irreducible.

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;
}

def fraction(p, q):
    a = []
    while q:
        a.append(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)$ нь доод бүрхүүлийн орой болно.

Бүрхүүл дээрх бүх бүхэл тоон орой нь

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

байх $(q;p)$ хэлбэрээр гарна, энд $t$ нь $0 \leq t \leq a_k$ байх бүхэл тоо. Өөрөөр хэлбэл бүрхүүл дээрх торон цэгүүдийн олонлог нь хагас ойртох бутархайнуудын олонлогтой харгалзана.

Доорх зурагт $r=\frac{9}{7}$-ийн ойртох бутархай ба хагас ойртох бутархайг (завсрын саарал цэгүүд) харуулав.

Хамгийн сайн ойролцоолол

Ямар нэг $x$-ийн хувьд $q \leq x$ нөхцөлийн дор $\left|r-\frac{p}{q}\right|$-ийг хамгийн бага болгодог бутархайг $\frac{p}{q}$ гэе.

Тэгвэл $\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}).$$

Implementation

We will compute the convergents as a pair of sequences $p_{-2}, p_{-1}, p_0, p_1, \dots, p_k$ and $q_{-2}, q_{-1}, q_0, q_1, \dots, q_k$:

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);
}

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

Гинжин бутархайн модууд

Бүх боломжит гинжин бутархайг ашигтай модон бүтцэд нэгтгэх хоёр үндсэн арга бий.

Штерн-Брокотын мод

Штерн-Брокотын мод нь ялгаатай бүх эерэг рационал тоог агуулсан хоёртын хайлтын мод юм.

Мод нь ерөнхийдөө дараах байдалтай харагдана:

The image by Aaron Rotenberg is licensed under CC BY-SA 3.0

$\frac{0}{1}$ ба $\frac{1}{0}$ бутархайг модны зүүн ба баруун талд харгалзан "виртуалаар" байлгана.

Тэгвэл зангилаа дахь бутархай нь түүний дээр орших $\frac{a}{b}$ ба $\frac{c}{d}$ гэсэн хоёр бутархайн медиант $\frac{a+c}{b+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_k > 1$ үед энэ нь $[a_0; a_1, \dots, a_k-1,1]$, харин $a_k = 1$ үед $[a_0; a_1, \dots, a_{k-1}, 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 < B$ эсэхийг тогтоохын тулд баруун бууралт дээр байвал $a_k < b_k$ эсэхийг, зүүн бууралт дээр байвал $a_k > b_k$ эсэхийг шалгана.

Өөрөөр хэлбэл иррационал $A$ ба $B$-ийн хувьд лексикографын харьцуулалтаар $(a_0, -a_1, a_2, -a_3, \dots) < (b_0, -b_1, b_2, -b_3, \dots)$ байх ба зөвхөн тэр үед л $A < B$ болно.

Одоо $\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$-ийн тэгш сондгой байдлаар эсвэл тэдгээрийг иррационал тоо мэт харьцуулж тодорхойлж болно.

# check if a < b assuming that a[-1] = b[-1] = infty and 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: # empty a = inf
        a[-1] -= 1
        a.append(1)
    return a

# return 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}$ өгөгдсөн. $(q; p)$ нь лексикографын дарааллаар хамгийн бага бөгөөд $\frac{p_0}{q_0} < \frac{p}{q} < \frac{p_1}{q_1}$ байх $\frac{p}{q}$ рационал тоог ол.

Шийдэл

Штерн-Брокотын модны хэллэгээр энэ нь бид $\frac{p_0}{q_0}$ ба $\frac{p_1}{q_1}$-ийн хамгийн бага нийтлэг өвгийг (LCA) олох хэрэгтэй гэсэн үг. Штерн-Брокотын мод ба гинжин бутархайн хоорондын холбооноос болж энэ 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$-ийн гинжин бутархайн илэрхийллийг ашиглаж болно.

# finds lexicographically smallest (q, p)
# such that 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)$ өгөгдсөн. $C_i x + J_i y$ нь чанд өсөх дараалал болох $(x, y)$ эерэг бүхэл тооны хосыг олох хэрэгтэй.

Ийм хосуудын дундаас лексикографын дарааллаар хамгийн багыг нь ол.

Шийдэл

Нөхцөлийг өөрөөр томьёолбол бүх $i$-ийн хувьд $A_i x + B_i y$ эерэг байх ёстой, энд $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{-A_i}{B_i}$-ийг $\frac{p_0}{q_0}$, гурав дахь бүлгээс хамгийн бага $\frac{A_i}{-B_i}$-ийг $\frac{p_1}{q_1}$ гэе.

Одоо бодлого нь $\frac{p_0}{q_0} < \frac{p_1}{q_1}$ өгөгдсөн үед $(q;p)$ нь лексикографын дарааллаар хамгийн бага бөгөөд $\frac{p_0}{q_0} < \frac{p}{q} < \frac{p_1}{q_1}$ байх $\frac{p}{q}$ бутархайг олоход оршино.

    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)

Калкин-Вилфийн мод

Гинжин бутархайг хоёртын модонд зохион байгуулах арай хялбар арга бол Калкин-Вилфийн мод юм.

Мод нь ерөнхийдөө дараах байдалтай харагдана:

The image by Olli Niemitalo, Proz is licensed under CC0 1.0

Модны үндэст $\frac{1}{1}$ тоо байрлана. Дараа нь $\frac{p}{q}$ тоотой оройн хүүхдүүд нь $\frac{p}{p+q}$ ба $\frac{p+q}{q}$ болно.

Штерн-Брокотын модноос ялгаатай нь Калкин-Вилфийн мод бол хоёртын хайлтын мод биш тул түүнийг ашиглан рационал тоон дээр хоёртын хайлт хийж болохгүй.

Калкин-Вилфийн модонд $\frac{p}{q}$ бутархайн шууд эцэг нь $p>q$ үед $\frac{p-q}{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}$ болно.

Нөгөө талаас $p > q$ үед $s_k = \frac{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}}$ буюу $a_0 > 0$ үед $[0, 1, a_0, a_1, \dots, a_k]$, $a_0=0$ үед $[0, a_1+1, a_2, \dots, a_k]$ болно.

Тэмдэглэхэд, Калкин-Вилфийн модны оройнуудыг өргөнөөр эхлэх хайлтын дарааллаар дугаарлавал (өөрөөр хэлбэл үндэс нь $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}$-ийн хүртвэрийн эсрэг тэмдэгтэй байна. Энэ нь эргээд

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

-ийн хувьд $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}}$$

нь $q_i q_{i-1}$ хэр хурдан буурахаас хамаарч $(-1)^k$-тай ижил тэмдэгтэй байна. Иймээс тэгш дугаартай $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$ өгөгдсөн. $Ax + By = C$ байх $x, y \in \mathbb Z$-ийг ол.

Шийдэл

Энэ бодлогыг ихэвчлэн өргөтгөсөн Евклидийн алгоритм-аар боддог ч гинжин бутархай ашигласан энгийн бөгөөд шууд шийдэл бий.

$\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}$ болно.

# return (x, y) such that Ax+By=C
# assumes that such (x, y) exists
def dio(A, B, C):
    p, q = convergents(fraction(A, B))
    C //= A // p[-1] # divide by gcd(A, B)
    t = (-1) if len(p) % 2 else 1
    return t*C*q[-2], -t*C*p[-2]

Шугаман бутархай хувиргалт

Гинжин бутархайн өөр нэг чухал ойлголт бол шугаман бутархай хувиргалт хэмээх зүйл юм.

Тодорхойлолт

Шугаман бутархай хувиргалт гэдэг нь ямар нэг $a,b,c,d \in \mathbb R$-ийн хувьд $f(x) = \frac{ax+b}{cx+d}$ байх $f : \mathbb R \to \mathbb R$ функц юм.

$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}$ шугаман бутархай хувиргалтуудын $(L_0 \circ L_1)(x) = L_0(L_1(x))$ композиц нь өөрөө шугаман бутархай хувиргалт болно:

$$\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).$$

-ийг тооцоолоход хүрч буурна. Хувиргалтуудын композиц нь associative тул хэрчмийн модны зангилаа бүрт түүний дэд мод дахь хувиргалтуудын композицыг тооцоолж болно.

Гинжин бутархайн шугаман бутархай хувиргалт

$L(x) = \frac{ax+b}{cx+d}$ байг. $A=[a_0; a_1, \dots, a_n]$-ийн хувьд $L(A)$-ийн $[b_0; b_1, \dots, b_m]$ гинжин бутархайн илэрхийллийг тооцоол.

Энэ нь дурын $\frac{p}{q}$-ийн хувьд $A + \frac{p}{q} = \frac{qA + p}{q}$ ба $A \cdot \frac{p}{q} = \frac{p A}{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}.$$

Тодорхойлолт

Ямар нэг $k$-ийн хувьд $x = [a_0; a_1, \dots, a_k, x]$ байвал $x = [a_0; a_1, \dots]$ гинжин бутархайг үечилсэн гэж нэрлэнэ.

$y$ нь үечилсэн байхад $x = [a_0; a_1, \dots, a_k, y]$ байвал $x = [a_0; a_1, \dots]$ гинжин бутархайг эцэстээ үечилсэн гэж нэрлэнэ.

$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.$$

Ижил төстэй үндэслэл нь эцэстээ үечилсэн гинжин бутархайн хувьд буюу $y=[b_0; b_1, \dots, b_k, y]$ байхад $x = [a_0; a_1, \dots, a_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$ шийд нь эцэстээ үечилсэн гинжин бутархай болохыг батлаж болно (үүнийг анх Лагранж хийсэн).

Квадрат иррационал тоо

$x, y, z, n \in \mathbb Z$ ба $n > 0$ нь бүтэн квадрат биш байхад $\alpha = \frac{x+y\sqrt{n}}{z}$-ийн гинжин бутархайг ол.

Шийдэл

Тухайн тооны $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$ мэдэгдэж байгаа гэж үзээд $s_{k+1}$-ийг олъё.

Юуны өмнө $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$-ийн гинжин бутархайн илэрхийллийг тооцоолох код байна:

# compute the continued fraction of 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]$ гэвэл $0 \leq k \leq 10^9$-ийн хувьд $\frac{p_k}{q_k}=[a_0; a_1, \dots, a_k]$-ийг ол.

Шийдэл

$\sqrt x$-ийн үеийг тооцоолсны дараа гинжин бутархайн илэрхийллээс үүсэх шугаман бутархай хувиргалт дээр хоёртын зэрэгт дэвшүүлэлт ашиглан $a_k$-г тооцоолж болно. Үр дүнгийн хувиргалтыг олохын тулд $T$ хэмжээтэй үеийг нэг хувиргалт болгон шахаж, түүнийг $\lfloor \frac{k-1}{T}\rfloor$ удаа давтаад, дараа нь үлдсэн хувиргалтуудтай нь гараар нэгтгэнэ.

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

mod = 10**9+7

# compose (A[0]*x + A[1]) / (A[2]*x + A[3]) and (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 # period of a

# apply ak + 1/x = (ak*x+1)/(1x+0) to (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]))

Геометр тайлал

$r_k = \frac{p_k}{q_k}$ ойртох бутархайн хувьд $\vec r_k = (q_k;p_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 p$ вектор дээр $\vec r_{k-1}$-ийг нэмэх бүрд $\vec p \times \vec r$-ийн утга $\vec r_{k-1} \times \vec r$-ээр нэмэгдэнэ.

Тиймээс $a_k=\lfloor s_k \rfloor$ нь $\vec r$-тэй үүсгэх вектор үржвэрийн тэмдгийг өөрчлөхгүйгээр $\vec r_{k-2}$ дээр нэмж болох $\vec r_{k-1}$ векторын хамгийн их бүхэл тоо юм.

Өөрөөр хэлбэл $a_k$ нь $\vec r$-ээр тодорхойлогдох шулууныг давахгүйгээр $\vec r_{k-1}$-ийг $\vec r_{k-2}$ дээр нэмж болох хамгийн их бүхэл тоо юм:

$r=\frac{7}{9}=[0;1,3,2]$-ийн ойртох бутархайнууд. Хагас ойртох бутархайнууд нь саарал сумнуудын хоорондох завсрын цэгүүдтэй харгалзана.

Дээрх зурагт $\vec r_2 = (4;3)$-ыг $\vec r_0 = (1;0)$ дээр $\vec r_1 = (1;1)$-ийг давтан нэмж гаргаж авсан байна.

$y=rx$ шулууныг давахгүйгээр $\vec r_0$ дээр $\vec r_1$-ийг цаашид нэмэх боломжгүй болоход бид нөгөө тал руу шилжиж, $\vec r_1$ дээр $\vec r_2$-ыг давтан нэмж $\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$ ба $0 \leq t \leq a_k$ байх бүх бүхэл $t$-ийн хувьд $\vec r_{k-2} + t \cdot \vec r_{k-1}$ гэсэн үг. Бүх боломжит $k$-ийн хувьд нэгтгэвэл энэ нь тэгш ба сондгой дугаартай ойртох векторуудын үүсгэсэн олон өнцөгтүүдийн хоорондох зайд бүхэл цэг байхгүй гэсэн үг болно.

Энэ нь эргээд сондгой коэффициенттэй $\vec r_k$ нь $y=rx$ шулууны дээрх $x \geq 0$ байх торон цэгүүдийн гүдгэр бүрхүүлийг, харин тэгш коэффициенттэй $\vec r_k$ нь $y=rx$ шулууны доорх $x > 0$ байх торон цэгүүдийн гүдгэр бүрхүүлийг үүсгэнэ гэсэн үг.

Тодорхойлолт

Эдгээр олон өнцөгтийг гинжин бутархайн энэхүү геометр тайллыг анх санал болгосон Феликс Клейний нэрээр Клейний олон өнцөгт гэж бас нэрлэдэг.

Бодлогын жишээ

Хамгийн чухал баримт, ойлголтуудыг танилцуулсан тул одоо тодорхой бодлогын жишээ рүү орох цаг болов.

Шулууны доорх гүдгэр бүрхүүл

$r=[a_0;a_1,\dots,a_k]=\frac{p_k}{q_k}$-ийн хувьд $0 \leq x \leq N$ ба $0 \leq y \leq rx$ байх $(x;y)$ торон цэгүүдийн гүдгэр бүрхүүлийг ол.

Шийдэл

Хэрэв бид $0 \leq x$ гэсэн хязгааргүй олонлогийг авч үзэж байсан бол дээд гүдгэр бүрхүүлийг $y=rx$ шулуун өөрөө өгөх байсан.

Гэвч $x \leq N$ гэсэн нэмэлт хязгаарлалттай үед зөв гүдгэр бүрхүүлийг хадгалахын тулд бид эцэст нь шулуунаас хазайх шаардлагатай болно.

$t = \lfloor \frac{N}{q_k}\rfloor$ гэвэл бүрхүүл дээрх $(0;0)$-ийн дараах эхний $t$ торон цэг нь $1 \leq \alpha \leq t$ байх бүхэл $\alpha$-ийн хувьд $\alpha \cdot (q_k; p_k)$ болно.

Гэвч $(t+1)q_k$ нь $N$-ээс их учраас $(t+1)(q_k; p_k)$ нь дараагийн торон цэг байж чадахгүй.

Бүрхүүл дэх дараагийн торон цэгүүдэд хүрэхийн тулд бид $x \leq N$-ийг хадгалангаа $y=rx$-ээс хамгийн бага зайгаар хазайх $(x;y)$ цэг рүү очих хэрэгтэй.

$0 \leq x \leq 19$-ийн хувьд $y=\frac{4}{7}x$-ийн доорх торон цэгүүдийн гүдгэр бүрхүүл нь $(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)$ нь $\Delta x \leq N - x$ ба $\Delta y \leq r \Delta x$ нөхцөлийн дор $r \Delta x - \Delta y$-г хамгийн их болгоно.

Ийм цэгүүд нь $y=rx$-ийн доорх торон цэгүүдийн гүдгэр бүрхүүл дээр оршино. Өөрөөр хэлбэл $(\Delta x; \Delta y)$ нь $r$-ийн доод хагас ойртох бутархай байх ёстой.

Иймд $(\Delta x; \Delta y)$ нь ямар нэг сондгой $i$ тоо ба $0 \leq t < a_i$-ийн хувьд $(q_{i-1}; p_{i-1}) + t \cdot (q_i; p_i)$ хэлбэртэй байна.

Ийм $i$-г олохын тулд бид хамгийн ихээс нь эхлэн бүх боломжит $i$-г туулж, $N-x-q_{i-1} \geq 0$ байх $i$-ийн хувьд $t = \lfloor \frac{N-x-q_{i-1}}{q_i} \rfloor$-ийг ашиглаж болно.

$(\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$-ээс их байна.

Одоо бид $N$-ээс хэтрэхээс өмнө $(x;y)$ дээр $(\Delta x; \Delta y)$-г $k = \lfloor \frac{N-x}{\Delta x} \rfloor$ удаа нэмж болох ба үүний дараа дараагийн хагас ойртох бутархайг оролдоно.

// returns [ah, ph, qh] such that points r[i]=(ph[i], qh[i]) constitute upper convex hull
// of lattice points on 0 <= x <= N and 0 <= y <= r * x, where r = [a0; a1, a2, ...]
// and there are ah[i]-1 integer points on the segment between r[i] and r[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);
}

# returns [ah, ph, qh] such that points r[i]=(ph[i], qh[i]) constitute upper convex hull
# of lattice points on 0 <= x <= N and 0 <= y <= r * x, where r = [a0; a1, a2, ...]
# and there are ah[i]-1 integer points on the segment between r[i] and r[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

Timus - Crime and Punishment

Танд $A$, $B$, $N$ бүхэл тоонууд өгөгдсөн. $Ax + By \leq N$ бөгөөд $Ax + By$ хамгийн их байх $x \geq 0$ ба $y \geq 0$-ийг ол.

Шийдэл

Энэ бодлогод $1 \leq A, B, N \leq 2 \cdot 10^9$ байх тул үүнийг $O(\sqrt N)$-ээр бодож болно. Гэвч гинжин бутархай ашигласан $O(\log N)$ шийдэл бий.

Тав тухтай байлгах үүднээс бид $x \mapsto \lfloor \frac{N}{A}\rfloor - x$ орлуулга хийж $x$-ийн чиглэлийг эсрэг болгоно. Ингэснээр одоо бид $0 \leq x \leq \lfloor \frac{N}{A} \rfloor$, $By - Ax \leq N \;\bmod\; A$ бөгөөд $By - Ax$ хамгийн их байх $(x; y)$ цэгийг олох хэрэгтэй болно. $x$ бүрийн хувьд оновчтой $y$ нь $\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$ коэффициентийг тооцоолохдоо үүнийг санаж байх ёстой.

# (x, y) such that y = (A*x+B) // C,
# Cy - Ax is max and 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

$e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, \dots, 1, 2n, 1, \dots]$ нь Эйлерийн тоо, $N \leq 10^{4000}$ байхад $\sum\limits_{x=1}^N \lfloor ex \rfloor$-ийг тооцоол.

Шийдэл

Энэ нийлбэр нь $1 \leq x \leq N$ ба $1 \leq y \leq ex$ байх $(x;y)$ торон цэгийн тоотой тэнцүү.

$y=ex$-ийн доорх цэгүүдийн гүдгэр бүрхүүлийг байгуулсны дараа энэ тоог Пикийн теорем ашиглан тооцоолж болно:

// sum floor(k * x) for k in [1, N] and x = [a0; a1, a2, ...]
int sum_floor(auto a, int N) {
    N++;
    auto [ah, ph, qh] = hull(a, N);

    // The number of lattice points within a vertical right trapezoid
    // on points (0; 0) - (0; y1) - (dx; y2) - (dx; 0) that has
    // a+1 integer points on the segment (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;
}

# sum floor(k * x) for k in [1, N] and x = [a0; a1, a2, ...]
def sum_floor(a, N):
    N += 1
    ah, ph, qh = hull(a, N)

    # The number of lattice points within a vertical right trapezoid
    # on points (0; 0) - (0; y1) - (dx; y2) - (dx; 0) that has
    # a+1 integer points on the segment (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

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.$$

болж хураагдана. Харин $x$-ийг $1$-ээс $N$ хүртэл авч $\lfloor rx \rfloor$-ийг нийлбэрлэх нь өмнөх бодлогоос бидний хийж чадах зүйл юм.

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

def solve(p, q, N):
    return p * N * (N + 1) // 2 - q * sum_floor(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]$ дээр өөр торон цэг байхгүй.

Иймд $[0, N-1]$ дээрх $y=\frac{Ax+B}{M}$ шулууны доорх бүтэн гүдгэр бүрхүүлийг байгуулахын тулд бид $[0, N-1]$ дээрх шулуунд хамгийн ойр цэг хүртэл байгуулж, дараа нь шулуун энэ цэгээр дайрч байгаа мэтээр $B=0$-тэй гүдгэр бүрхүүл байгуулах алгоритмыг дахин ашиглан үргэлжлүүлж болно:

# hull of lattice (x, y) such that 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

$1 \leq p, q \leq 10^9$ байх $\frac{p}{q}$ рационал тоо байна. Та хэд хэдэн $m$ анхны тооны хувьд $m \sim 10^9$ модулиар $p q^{-1}$-ийн утгыг асууж болно. $\frac{p}{q}$-г сэргээ.

Эквивалент томьёолол: $1 \leq x \leq N$-ийн хувьд $Ax \;\bmod\; M$-ийг хамгийн бага болгох $x$-ийг ол.

Шийдэл

Хятадын үлдэгдлийн теоремоор хэд хэдэн анхны тооны модулиар үр дүнг асуух нь тэдгээрийн үржвэрийн модулиар асуухтай ижил. Иймээс ерөнхий чанараа алдалгүйгээр бид хангалттай том $m$ тооны модулиар үлдэгдлийг мэднэ гэж үзнэ.

Өгөгдсөн $r$ үлдэгдлийн хувьд $p \equiv qr \pmod m$-д хэд хэдэн боломжит $(p, q)$ шийд байж болно. Гэвч $(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}$-ийн хувьд энэ нь $1 \leq p, q \leq 10^9$ байх $\frac{p}{q}$ шийд рационал тооны хувьд цор ганц гэсэн үг.

Тиймээс бодлого нь $m$ модулиар $r$ өгөгдсөн үед $1 \leq q \leq 10^9$ ба $qr \;\bmod\; m \leq 10^9$ байх дурын $q$-г олоход хүрч буурна.

Энэ нь үндсэндээ $1 \leq q \leq 10^9$-ийн хувьд $qr \bmod m$-ийг хамгийн бага болгох $q$-г олохтой ижил.

$qr = km + b$-ийн хувьд энэ нь бид $1 \leq q \leq 10^9$ ба $qr - km \geq 0$ хамгийн бага байх $(q, m)$ хосыг олох хэрэгтэй гэсэн үг.

$m$ нь тогтмол тул бид түүнд хувааж, цаашид үүнийг $1 \leq q \leq 10^9$ ба $\frac{r}{m} q - k \geq 0$ хамгийн бага байх $q$-г ол гэж дахин томьёолж болно.

Гинжин бутархайн хэллэгээр энэ нь $\frac{k}{q}$ нь $\frac{r}{m}$-ийн хамгийн сайн Диофантын ойролцоолол болох ба зөвхөн $\frac{r}{m}$-ийн доод хагас ойртох бутархайг шалгахад хангалттай гэсэн үг.

# find Q that minimizes Q*r mod m for 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]

Дасгал бодлогууд