پرش به محتویات

کسرهای مسلسل

کسر مسلسل (Continued fraction) نمایشی از یک عدد حقیقی به صورت یک دنباله همگرای خاص از اعداد گویا است. این کسرها در برنامه‌نویسی رقابتی مفید هستند، زیرا محاسبه آن‌ها آسان است و می‌توان از آن‌ها برای یافتن بهترین تقریب گویای ممکن برای یک عدد حقیقی (در میان تمام اعدادی که مخرجشان از یک مقدار معین تجاوز نمی‌کند) به طور مؤثر استفاده کرد.

علاوه بر این، کسرهای مسلسل ارتباط نزدیکی با الگوریتم اقلیدس دارند که آن‌ها را در مجموعه‌ای از مسائل نظریه اعداد مفید می‌سازد.

نمایش کسر مسلسل

تعریف

فرض کنید $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} $$

می‌توان ثابت کرد که هر عدد گویایی را می‌توان دقیقاً به ۲ روش به صورت کسر مسلسل نمایش داد:

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

علاوه بر این، طول $k$ چنین کسر مسلسلی برای $r=\frac{p}{q}$ به صورت $k = O(\log \min(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$ همگراهای (convergents) $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}$ تعریف می‌شود. از فرمول Binet می‌دانیم که:

$$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$ نیم‌همگرا (semiconvergents) نامیده می‌شوند.

ما معمولاً به (نیم)همگراهایی که بزرگتر از $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=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]$. از این رو، همگراها همیشه کسرهای ساده‌نشدنی هستند.

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)$ رئوس پوش پایینی هستند.

تمام رئوس صحیح روی پوش‌ها به صورت $(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$ محاسبه خواهیم کرد:

auto convergents(vector<int> a) {
    vector<long long> p = {0, 1};
    vector<long long> q = {1, 0};
    for(auto it: a) {
        p.push_back(p.back() * it + p[p.size() - 2]);
        q.push_back(q.back() * 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

درخت‌های کسرهای مسلسل

دو راه اصلی برای ادغام تمام کسرهای مسلسل ممکن در ساختارهای درختی مفید وجود دارد.

درخت اشترن-بروکوت (Stern-Brocot)

درخت اشترن-بروکوت یک درخت جستجوی دودویی است که شامل تمام اعداد گویای مثبت متمایز است.

درخت به طور کلی به شکل زیر است:

تصویر از 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_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]$.

بیایید درخت اشترن-بروکوت را اندیس‌گذاری کنیم. به رأس ریشه اندیس ۱ اختصاص داده می‌شود. سپس برای یک رأس $v$، اندیس فرزند چپ آن با تغییر بیت پیشروی $v$ از ۱ به ۱۰ و برای فرزند راست، با تغییر بیت پیشرو از ۱ به ۱۱ اختصاص داده می‌شود:

در این اندیس‌گذاری، نمایش کسر مسلسل یک عدد گویا، کدگذاری طول اجرا اندیس دودویی آن را مشخص می‌کند.

برای $\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]$ است.

شایان ذکر است که درخت اشترن-بروکوت، در واقع یک treap است. یعنی، از نظر مقدار $\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$ یا با مقایسه آن‌ها به عنوان اعداد گنگ تعیین می‌شود.

# بررسی می‌کند که آیا 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$ که در مسئله قبلی به دست آمد، استفاده کرد.

# کوچکترین (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}$.

    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)

درخت کالکین-ویلف (Calkin-Wilf)

یک راه تا حدودی ساده‌تر برای سازماندهی کسرهای مسلسل در یک درخت دودویی، درخت کالکین-ویلف است.

درخت به طور کلی به این شکل است:

تصویر از Olli Niemitalo, Proz تحت مجوز 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}$.

از طرف دیگر، اگر به طور مکرر از $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}}$، که برای $a_0 > 0$ برابر با $[0, 1, a_0, a_1, \dots, a_k]$ و برای $a_0=0$ برابر با $[0, a_1+1, a_2, \dots, a_k]$ است.

شایان ذکر است، اگر رئوس درخت کالکین-ویلف را به ترتیب جستجوی سطح-اول شماره‌گذاری کنیم (یعنی ریشه عدد ۱ دارد و فرزندان رأس $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},$$

برابر با ۱ است، بنابراین

$$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$ دارید. اعداد صحیح $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}$ است.

# (x, y) را برمی‌گرداند به طوری که Ax+By=C
# فرض می‌شود که چنین (x, y) وجود دارد
def dio(A, B, C):
    p, q = convergents(fraction(A, B))
    C //= A // p[-1] # تقسیم بر ب.م.م(A, B)
    t = -1 if len(p) % 2 == 0 else 1 # در متن اصلی (-1)^(k-1) بود. len(p) = k+3. پس k-1 زوج است اگر len(p) فرد باشد
    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_m] = [a_0; a_1, \dots, a_k, [b_0; b_1, \dots, b_m]]$. در اینجا $b_0$ باید جایگزین $x$ شود.

بیایید $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]$ متناوب (periodic) نامیده می‌شود اگر $x = [a_0; a_1, \dots, a_k, x]$ برای یک $k$ معین.

یک کسر مسلسل $x = [a_0; a_1, \dots]$ در نهایت متناوب (eventually periodic) نامیده می‌شود اگر $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_m, 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$ اشتباه است. باید $\lfloor \frac{x_k + y_k \sqrt n}{z_k} \rfloor$ باشد. اما چون $y_k \sqrt n$ گنگ است، محاسبه آن دشوار است. در کد از $\lfloor \frac{x_k + y_k \lfloor \sqrt n \rfloor}{z_k} \rfloor$ استفاده شده که برای $\alpha = \sqrt n$ کار می‌کند.

$$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 - z_k a_k) - y_k z_k \sqrt n}{(x_k - z_k a_k)^2 - y_k^2 n}.$$

بنابراین، اگر $t_k = x_k - z_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}$ را بر بزرگترین مقسوم‌علیه مشترکشان ساده کنیم، نتیجه منحصر به فرد خواهد بود. بنابراین، می‌توانیم از آن برای بررسی اینکه آیا حالت فعلی قبلاً تکرار شده است و همچنین برای بررسی اینکه اندیس قبلی که این حالت را داشته، کجا بوده است، استفاده کنیم.

در کد زیر، $a_k$ به صورت (x * n0 + y) // z محاسبه می‌شود که برای $\sqrt n$ صحیح است چون در آن حالت $x, y, z$ ضرایب $\frac{x\sqrt n + y}{z}$ هستند. کد زیر برای محاسبه نمایش کسر مسلسل $\alpha = \sqrt n$ است:

import math
# محاسبه کسر مسلسل sqrt(n)
def sqrt_cf(n):
    if int(math.sqrt(n))**2 == n:
        return [int(math.sqrt(n))]

    m = 0
    d = 1
    a0 = int(math.sqrt(n))
    a = [a0]

    seen = {}

    while (m, d) not in seen:
        seen[(m,d)] = len(a)
        m = d * a[-1] - m
        d = (n - m**2) // d
        a.append(int((a0 + m) / d))

    start_period = seen[(m, d)]
    return a[:start_period], a[start_period:] # پیش‌دوره، دوره

با استفاده از تابع 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$ بار تکرار می‌کنید، پس از آن به صورت دستی آن را با تبدیلات باقیمانده ترکیب می‌کنید.

# کد با فرض وجود تابع sqrt_cf از مثال قبل
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):
    # A, B ماتریس‌های 2x2 هستند
    # (a b) (e f) = (ae+bg af+bh)
    # (c d) (g h)   (ce+dg cf+dh)
    return [ (A[0]*B[0]+A[1]*B[2]) % mod, (A[0]*B[1]+A[1]*B[3]) % mod, 
             (A[2]*B[0]+A[3]*B[2]) % mod, (A[2]*B[1]+A[3]*B[3]) % mod ]

def bpow(A, n):
    res = [1, 0, 0, 1] # ماتریس همانی
    base = A
    while n > 0:
        if n % 2 == 1:
            res = combine(res, base)
        base = combine(base, base)
        n //= 2
    return res

pre_period, period = sqrt_cf(x)

# تبدیل نهایی: p_k / q_k
# [a_0; a_1, ..., a_k]
# p_k = a_k p_{k-1} + p_{k-2}
# q_k = a_k q_{k-1} + q_{k-2}
# (p_k) = (a_k 1) (p_{k-1})
# (q_k)   (1  0) (q_{k-1})

# ماتریس برای کل تبدیل
final_matrix = [1, 0, 0, 1]

# بخش پیش‌دوره
k_rem = k
for i in range(len(pre_period)):
    if k_rem < 0: break
    mat_a = [pre_period[i], 1, 1, 0]
    final_matrix = combine(final_matrix, mat_a)
    k_rem -= 1

if k_rem >= 0:
    # ماتریس برای یک دوره کامل
    period_matrix = [1, 0, 0, 1]
    for val in period:
        mat_a = [val, 1, 1, 0]
        period_matrix = combine(period_matrix, mat_a)

    num_periods = (k_rem + 1) // len(period)
    final_matrix = combine(final_matrix, bpow(period_matrix, num_periods))
    k_rem -= num_periods * len(period)

    # بخش باقیمانده دوره
    for i in range(k_rem + 1):
        mat_a = [period[i], 1, 1, 0]
        final_matrix = combine(final_matrix, mat_a)

# [p_k, p_{k-1}], [q_k, q_{k-1}]
# p_{-2}=0, p_{-1}=1
# q_{-2}=1, q_{-1}=0
pk = final_matrix[0] * 1 + final_matrix[1] * 0
qk = final_matrix[2] * 1 + final_matrix[3] * 0

print(str(pk % mod) + '/' + str(qk % mod))

تعبیر هندسی

فرض کنید $\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_k;p_k) \times (1;r) = q_k r - p_k$، بنابراین

$$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 = (3;4)$ با افزودن مکرر $\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 = (7;9)$ را به دست آوریم.

این روش بردارهای به طور نمایی طولانی‌تری تولید می‌کند که به خط نزدیک می‌شوند.

به دلیل این ویژگی، روش تولید بردارهای همگرای متوالی توسط بوریس دلونی الگوریتم کشیدن بینی نامیده شده است.

اگر به مثلثی که روی نقاط $\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$ تجاوز کنیم، پس از آن نیم‌همگرای بعدی را امتحان خواهیم کرد.

// [ah, ph, qh] را برمی‌گرداند به طوری که نقاط r[i]=(qh[i], ph[i]) پوش محدب بالایی را تشکیل می‌دهند
// از نقاط مشبکه روی 0 <= x <= N و 0 <= y <= r * x، که r = [a0; a1, a2, ...]
// و ah[i] نقطه صحیح روی پاره‌خط بین r[i-1] و r[i] وجود دارد.
auto hull(auto a, long long N) {
    auto [p, q] = convergents(a);
    long long t = N / q.back();
    vector<long long> ah = {t};
    vector<long long> ph = {0, t * p.back()};
    vector<long long> qh = {0, t * q.back()};

    for(int i = q.size() - 2; i >= 0; i--) {
        if(i % 2) {
            while(qh.back() + q[i - 1] <= N) {
                t = (N - qh.back() - q[i - 1]) / q[i];
                long long dp = p[i - 1] + t * p[i];
                long long dq = q[i - 1] + t * q[i];
                long long 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);
}

# [ah, ph, qh] را برمی‌گرداند به طوری که نقاط r[i]=(qh[i], ph[i]) پوش محدب بالایی را تشکیل می‌دهند
# از نقاط مشبکه روی 0 <= x <= N و 0 <= y <= r * x، که r = [a0; a1, a2, ...]
# و ah[i] نقطه صحیح روی پاره‌خط بین r[i-1] و r[i] وجود دارد.
def hull(a, N):
    p, q = convergents(a)
    t = N // q[-1]
    ah = [t]
    ph = [0, t*p[-1]]
    qh = [0, t*q[-1]]
    # p,q شامل p_(-2), p_(-1) هستند، پس اندیس همگراها با اندیس آرایه متفاوت است
    for i in reversed(range(2, len(q))):
        # همگراهای پایینی (که r_k < r) اندیس k فرد دارند
        # اندیس در آرایه: k+2
        if (i-2) % 2 == 1:
            # q[i-2] = q_{i-4}, q[i-1] = q_{i-3}
            # ما به q_{j} و q_{j-1} نیاز داریم که j فرد است. پس q[i], q[i-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$ را دارید. $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 \pmod 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$ نیم‌همگرا این را در نظر داشته باشید.

# (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)
    # نقطه شروع (0, B//C)
    best_x, best_y = 0, B//C
    curr_x, curr_y = 0, B//C

    # همگراهای بالایی (k زوج)
    for i in range(2, len(q)):
        if (i-2) % 2 == 0:
            # امتحان q[i] و q[i-1]
            dq, dp = q[i], p[i]
            if curr_x + dq > N:
                # امتحان نیم‌همگراهای بین r_{i-2} و r_i
                dq_s, dp_s = q[i-1], p[i-1]
                if curr_x + dq_s <= N:
                    # حداکثر ضریب t
                    t = (N - curr_x - dq_s) // dq

                    # ضریب t برای اینکه از خط عبور نکنیم
                    if diff(dq, dp) < 0:
                        t = min(t, (B - diff(curr_x+dq_s, curr_y+dp_s)) // abs(diff(dq, dp)))

                    curr_x += dq_s + t*dq
                    curr_y += dp_s + t*dp
                    if diff(curr_x, curr_y) > diff(best_x, best_y):
                        best_x, best_y = curr_x, curr_y
                break

            # ضریب k برای اینکه از خط عبور نکنیم
            k = (N-curr_x) // dq
            if diff(dq, dp) < 0:
                k = min(k, (B - diff(curr_x, curr_y)) // abs(diff(dq, dp)))

            curr_x += k*dq
            curr_y += k*dp
            if diff(curr_x, curr_y) > diff(best_x, best_y):
                best_x, best_y = curr_x, curr_y
            if k < (N-curr_x) // dq : # نتوانستیم کامل پیش برویم
                break
    return best_x, best_y

def solve_crime(A, B, N):
    if N < 0: return 0, 0
    # max (Ax+By) s.t. Ax+By <= N
    # بدون از دست دادن کلیت A <= B
    if A > B: A, B = B, A
    if A == 0: return 0, N//B

    # x_new = N/A - x, y_new = y
    # A(N/A - x) + By <= N -> N-Ax+By <= N -> By - Ax <= 0
    # می خواهیم By - Ax را بیشینه کنیم
    x, y = closest(B, 0, A, N // B)

    return (N - B*y) // A, 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$، این تعداد را می‌توان با استفاده از قضیه پیک محاسبه کرد:

// مجموع floor(r * x) برای x از 1 تا N و r = [a0; a1, a2, ...]
long long sum_floor(auto a, long long 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 = [](long long y1, long long y2, long long dx, long long a) {
        long long b = y1 + y2 + a + dx; // نقاط مرزی
        long long A = (y1 + y2) * dx; // دو برابر مساحت
        return (A - b + 2) / 2 + b - (y2 + 1); // نقاط داخلی + نقاط روی دو ضلع
    };

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

# مجموع floor(r * x) برای x از 1 تا N و r = [a0; a1, a2, ...]
def sum_floor_func(a, N):
    # N شامل خود نقطه پایانی نیست
    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

    ans = 0
    for i in range(1, len(qh)):
        # مجموع floor(r*x) برای qh[i-1] < x <= qh[i]
        y_start = ph[i-1]
        y_end = ph[i]
        x_start = qh[i-1]
        x_end = qh[i]
        dx = x_end - x_start
        # تعداد نقاط روی پاره‌خط از (x_start, y_start) تا (x_end, y_end) برابر است با
        # gcd(dx, dy) + 1. در اینجا ah[i-1] تعداد پله هاست.
        ans += picks(y_start, y_end, dx, ah[i-1])

    return ans - (N + 1)

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$ چیزی است که ما از مسئله قبلی قادر به انجام آن هستیم.

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

def solve_mod_sum(p, q, N):
    return p * N * (N + 1) // 2 - q * sum_floor_func(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$ دوباره استفاده کنیم:

# پوش محدب نقاط مشبکه (x, y) به طوری که M*y <= A*x+B
def general_hull(A, B, M, N):
    a = fraction(A, M)
    p, q = convergents(a)
    ah = []
    ph = [B // M]
    qh = [0]

    # پیدا کردن نزدیکترین نقطه
    curr_x, curr_y = 0, B // M
    best_x, best_y = 0, B // M
    max_diff = M * curr_y - A * curr_x

    for i in range(2, len(q)):
        if (i-2) % 2 == 0: # همگراهای بالایی
            dq, dp = q[i], p[i]
            if curr_x + dq >= N:
                # نیم‌همگراها
                dq_s, dp_s = q[i-1], p[i-1]
                if curr_x + dq_s < N:
                    t = (N - 1 - curr_x - dq_s) // dq
                    # بررسی عبور از خط
                    if M*dp - A*dq < 0:
                        t = min(t, (B - (M* (curr_y+dp_s) - A*(curr_x+dq_s))) // abs(M*dp-A*dq))
                    curr_x += dq_s + t*dq
                    curr_y += dp_s + t*dp
                    if M * curr_y - A * curr_x > max_diff:
                        best_x, best_y = curr_x, curr_y
                        max_diff = M * curr_y - A * curr_x
                break

            k = (N-1 - curr_x) // dq
            if M*dp - A*dq < 0:
                k = min(k, (B - (M*curr_y - A*curr_x)) // abs(M*dp - A*dq))
            curr_x += k*dq
            curr_y += k*dp
            if M*curr_y - A*curr_x > max_diff:
                best_x, best_y = curr_x, curr_y
                max_diff = M*curr_y - A*curr_x
            if k < (N-1-curr_x)//dq: break

    # محاسبه مجموع تا بهترین نقطه
    # ...
    # سپس مجموع از بهترین نقطه تا N
    # ... این راه حل پیچیده است. راه حل استاندارد برای این مسئله ساده تر است.
    # راه حل استاندارد:
    if A == 0: return (B // M) * N
    if A >= M: return (A // M) * N * (N - 1) // 2 + (B // M) * N + solve_floor_sum(N, M, A % M, B % M)
    if B >= M: return N * (B // M) + solve_floor_sum(N, M, A, B % M)
    m = (A * (N-1) + B) // M
    return (N - 1) * m - solve_floor_sum(m, A, M, -B - 1 + A)

def solve_floor_sum(N, M, A, B):
    # ... (کد کامل برای تابع بازگشتی)
    pass

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 \pmod 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$ باشند، آنگاه تفاوت حداکثر $2 \cdot 10^{18}$ است. برای $m > 2 \cdot 10^{18}$ این به این معناست که راه‌حل $\frac{p}{q}$ با $1 \leq p, q \leq 10^9$ به عنوان یک عدد گویا منحصر به فرد است.

بنابراین، مسئله به این خلاصه می‌شود که با داشتن $r$ به پیمانه $m$، هر $q$ را پیدا کنیم به طوری که $1 \leq q \leq 10^9$ و $qr \pmod m \leq 10^9$.

این عملاً همانند یافتن $q$ است که کمترین مقدار ممکن $qr \bmod m$ را برای $1 \leq q \leq 10^9$ به دست می‌دهد.

برای $qr = km + b$ این به این معناست که باید یک جفت $(q, k)$ پیدا کنیم به طوری که $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}$ را بررسی کنیم.

# پیدا کردن Q که Q*r mod m را برای 1 <= Q <= n < m کمینه می‌کند
def mod_min(r, n, m):
    a = fraction(r, m)
    p, q = convergents(a)
    min_val = m
    best_q = 1
    # بررسی همگراها
    for i in range(2, len(q)):
        if q[i] > n: break
        val = (q[i] * r) % m
        if val < min_val:
            min_val = val
            best_q = q[i]

    # بررسی نیم‌همگراهای آخرین همگرای معتبر
    # i-1 آخرین همگرایی است که q[i-1] <= n
    last_valid_i = i - 1
    if last_valid_i >= 2:
        # نیم‌همگراهای بین r_{i-3} و r_{i-2}
        # ما به همگراهای با اندیس زوج نیاز داریم (بالایی ها)
        # چون r - p/q < 0 -> rq - p < 0 (mod m)
        # ولی ما دنبال rq - mp > 0 هستیم پس همگراهای پایینی (اندیس فرد)
        if (last_valid_i - 2) % 2 == 1:
            prev_q, prev_p = q[last_valid_i-1], p[last_valid_i-1]
            curr_q, curr_p = q[last_valid_i], p[last_valid_i]

            t = (n - prev_q) // curr_q
            test_q = prev_q + t*curr_q
            val = (test_q*r)%m
            if val < min_val:
                min_val = val
                best_q = test_q

    return best_q, min_val

مسائل تمرینی