The problem gives five product totals for two suppliers' luxury hampers. To keep the algebra neutral, write those totals as
$$P=(5248,1312,2624,5760,3936),\qquad Q=(640,1888,3776,3776,5664).$$
Their grand totals are
$$T_P=18880,\qquad T_Q=15744.$$
We seek the largest rational number \(m>1\) for which one can choose positive integers \(p_i\) and \(q_i\) for all five products so that the same multiplicative bias \(m\) holds both product-by-product and after the five products are combined. The direct search over all five pairs \((p_i,q_i)\) is far too large, so the solution looks for structure in the fixed supplier totals.
Write the desired multiplier as \(m=\frac{u}{v}\) in lowest terms. The implementations turn the problem into an exact arithmetic feasibility test: first generate all possible rational candidates for \(m\), then decide which of them admit positive integer counts satisfying the product constraints and the global consistency equation.
For each product \(i\), the implementation works with positive integers \(p_i\) and \(q_i\) constrained by
$$vP_iq_i=uQ_ip_i.$$
The combined condition over all five products is
$$vT_Q\sum_{i=1}^{5}p_i=uT_P\sum_{i=1}^{5}q_i.$$
So a candidate \(m\) is valid if and only if these six integer equations can be satisfied simultaneously with every \(p_i,q_i\ge 1\).
From the first product we have \(P_1=5248\) and \(Q_1=640\), so
$$\frac{u}{v}=\frac{P_1q_1}{Q_1p_1}=\frac{5248\,q_1}{640\,p_1}=\frac{41q_1}{5p_1}.$$
Because \(1\le p_1\le P_1\) and \(1\le q_1\le Q_1\), every valid multiplier must appear among the reduced fractions
$$m=\frac{41b}{5a},\qquad 1\le a\le 5248,\quad 1\le b\le 640,\quad m>1.$$
This is the key finiteness argument: the search never needs to guess arbitrary rationals. It only needs to enumerate, reduce, sort, and deduplicate the fractions forced by product 1.
The five supplier ratios are not all different:
$$\frac{Q_1}{P_1}=\frac{5}{41},\qquad \frac{Q_2}{P_2}=\frac{Q_3}{P_3}=\frac{Q_5}{P_5}=\frac{59}{41},\qquad \frac{Q_4}{P_4}=\frac{59}{90}.$$
So the products split naturally into three groups:
$$G_0=\{1\},\qquad G_1=\{2,3,5\},\qquad G_2=\{4\}.$$
For a fixed candidate \(m=\frac{u}{v}\), let the base ratio of group \(g\) be \(\frac{\beta_g}{\alpha_g}\), so the three values are \(\frac{5}{41}\), \(\frac{59}{41}\), and \(\frac{59}{90}\). Reduce
$$\frac{u\beta_g}{v\alpha_g}=\frac{n_g}{d_g}$$
to lowest terms. Then every product \(i\in G_g\) must satisfy
$$\frac{q_i}{p_i}=\frac{uQ_i}{vP_i}=\frac{n_g}{d_g},$$
hence there is a positive integer \(t_i\) such that
$$p_i=d_gt_i,\qquad q_i=n_gt_i.$$
This is the central simplification: once \(m\) is fixed, each product contributes only one new integer parameter \(t_i\), and products that share the same supplier ratio also share the same pair \((n_g,d_g)\).
The chosen counts cannot exceed the supplier totals, so for every product \(i\in G_g\),
$$1\le t_i\le \min\left(\left\lfloor\frac{P_i}{d_g}\right\rfloor,\left\lfloor\frac{Q_i}{n_g}\right\rfloor\right).$$
Now define one sum per group:
$$s_g=\sum_{i\in G_g}t_i.$$
If a group contains \(|G_g|\) products, then the smallest possible value is
$$L_g=|G_g|,$$
because each \(t_i\ge 1\). The largest possible value is
$$H_g=\sum_{i\in G_g}\min\left(\left\lfloor\frac{P_i}{d_g}\right\rfloor,\left\lfloor\frac{Q_i}{n_g}\right\rfloor\right).$$
A useful observation is that every integer between \(L_g\) and \(H_g\) is achievable. There is no subset-sum complication here: all \(t_i\) move in steps of 1, so starting from the minimum assignment \(t_i=1\), we can increase variables one by one until any target group sum in the interval is reached.
Thus the five original parameters \(t_1,\dots,t_5\) can be replaced by the three interval-constrained sums
$$s_0\in[L_0,H_0],\qquad s_1\in[L_1,H_1],\qquad s_2\in[L_2,H_2],$$
with \(L_0=1\), \(L_1=3\), and \(L_2=1\).
Substituting \(p_i=d_gt_i\) and \(q_i=n_gt_i\) into the global condition gives
$$vT_Q\sum_{g=0}^{2}d_gs_g=uT_P\sum_{g=0}^{2}n_gs_g.$$
Move everything to one side and define
$$c_g=vT_Qd_g-uT_Pn_g.$$
Then \(m\) is feasible if and only if there exist integers \(s_0,s_1,s_2\) in their intervals such that
$$c_0s_0+c_1s_1+c_2s_2=0.$$
The implementation fixes \(s_0\) and rewrites the problem as
$$c_1s_1+c_2s_2=r,\qquad r=-c_0s_0.$$
If \(g=\gcd(c_1,c_2)\) does not divide \(r\), there is no solution. Otherwise, if
$$c_1x_0+c_2y_0=g,$$
then every solution is of the form
$$s_1=x_0\frac{r}{g}+\frac{c_2}{g}t,\qquad s_2=y_0\frac{r}{g}-\frac{c_1}{g}t,\qquad t\in\mathbb{Z}.$$
The remaining task is purely interval arithmetic: intersect the range of \(t\) forced by \(L_1\le s_1\le H_1\) with the range forced by \(L_2\le s_2\le H_2\). A non-empty intersection means the candidate \(m\) works.
The implementations ultimately find that the largest feasible multiplier is
$$m=\frac{123}{59}.$$
For this value, the three group reductions are
$$\frac{123\cdot 5}{59\cdot 41}=\frac{15}{59},\qquad \frac{123\cdot 59}{59\cdot 41}=3=\frac{3}{1},\qquad \frac{123\cdot 59}{59\cdot 90}=\frac{41}{30}.$$
So the group parameters are
$$ (d_0,n_0)=(59,15),\qquad (d_1,n_1)=(1,3),\qquad (d_2,n_2)=(30,41). $$
The corresponding upper bounds are
$$H_0=\min\!\left(\left\lfloor\frac{5248}{59}\right\rfloor,\left\lfloor\frac{640}{15}\right\rfloor\right)=42,$$
$$H_1=\min\!\left(\left\lfloor\frac{1312}{1}\right\rfloor,\left\lfloor\frac{1888}{3}\right\rfloor\right)+\min\!\left(\left\lfloor\frac{2624}{1}\right\rfloor,\left\lfloor\frac{3776}{3}\right\rfloor\right)+\min\!\left(\left\lfloor\frac{3936}{1}\right\rfloor,\left\lfloor\frac{5664}{3}\right\rfloor\right)=629+1258+1888=3775,$$
$$H_2=\min\!\left(\left\lfloor\frac{5760}{30}\right\rfloor,\left\lfloor\frac{3776}{41}\right\rfloor\right)=92.$$
The coefficients become
$$ (c_0,c_1,c_2)=(19971264,-6037824,-67344960)=464448\,(43,-13,-145). $$
So feasibility is equivalent to
$$43s_0-13s_1-145s_2=0.$$
One valid choice is
$$ (s_0,s_1,s_2)=(7,12,1), $$
because \(43\cdot 7-13\cdot 12-145\cdot 1=0\). The middle-group sum \(s_1=12\) is easy to realize, for example by taking the three product parameters there as \(1,1,10\). This concrete construction shows why \(\frac{123}{59}\) passes the feasibility test.
The C++, Python, and Java implementations follow the derivation directly. They never enumerate arbitrary five-tuples of product counts. Instead, they search the rational candidate set forced by the first product and test each candidate with exact integer arithmetic.
The implementation loops over all possible positive counts for product 1, forms the reduced fraction \(\frac{41b}{5a}\), discards candidates with \(m\le 1\), sorts the remaining fractions, and removes duplicates. This step constructs the complete finite search space.
For a fixed candidate \(m=\frac{u}{v}\), the implementation computes the three reduced group ratios \(\frac{n_g}{d_g}\), then the upper bound for each product and the interval \([L_g,H_g]\) for each group sum \(s_g\). If any product has no positive admissible value, the candidate is rejected immediately.
Otherwise it forms the coefficients \(c_g=vT_Qd_g-uT_Pn_g\), loops over all admissible \(s_0\), and for each one checks whether the remaining two-variable equation has a solution inside the intervals. That check uses the extended Euclidean algorithm together with interval tightening for the free parameter \(t\).
Each candidate can be tested independently. The C++ and Java implementations distribute those tests across multiple threads; the Python implementation performs the same arithmetic serially. After all feasible candidates are collected, the largest reduced fraction is returned.
Candidate generation starts from the \(5248\cdot 640=3{,}358{,}720\) raw fractions forced by product 1. Sorting and deduplicating them costs \(O(M\log M)\) with \(M=3{,}358{,}720\).
For each distinct candidate, the group preprocessing is constant-time, and the main loop scans only the possible values of \(s_0\). Since the first group contains a single product, \(s_0\) never ranges over more than a few hundred values. The two-variable Diophantine check is \(O(1)\) once the gcd and parameter intervals are computed. So the practical running time is dominated by candidate enumeration plus an \(O(C\cdot R)\) feasibility phase, where \(C\) is the number of distinct candidates and \(R\) is the width of the first group's interval. Memory usage is \(O(C)\) for storing the candidate list, plus constant auxiliary state for each test. Parallelism improves wall-clock time but does not change the asymptotic bounds.
Die Aufgabe gibt für fünf Produkttypen die Gesamtmengen zweier Lieferanten von Luxus-Hampern vor. Zur neutralen Notation schreiben wir diese Zahlen als
$$P=(5248,1312,2624,5760,3936),\qquad Q=(640,1888,3776,3776,5664).$$
Die Gesamtsummen sind
$$T_P=18880,\qquad T_Q=15744.$$
Gesucht ist die größte rationale Zahl \(m>1\), für die sich zu allen fünf Produkten positive ganze Zahlen \(p_i\) und \(q_i\) wählen lassen, sodass derselbe multiplikative Faktor \(m\) sowohl produktweise als auch nach dem Zusammenfassen aller fünf Produkte gilt. Eine rohe Suche über fünf unabhängige Zahlenpaare wäre viel zu groß; die Lösung nutzt deshalb die feste Struktur der gegebenen Liefermengen aus.
Schreibe den gesuchten Faktor als vollständig gekürzten Bruch \(m=\frac{u}{v}\). Die Implementierungen zerlegen das Problem in zwei Teile: zuerst alle möglichen rationalen Kandidaten für \(m\) erzeugen, danach für jeden Kandidaten exakt prüfen, ob positive ganze Zahlen existieren, die sowohl die Einzelbedingungen pro Produkt als auch die globale Konsistenzbedingung erfüllen.
Für jedes Produkt \(i\) arbeiten die Implementierungen mit positiven ganzen Zahlen \(p_i\) und \(q_i\), die
$$vP_iq_i=uQ_ip_i$$
erfüllen müssen. Die zusammengefasste Bedingung über alle fünf Produkte lautet
$$vT_Q\sum_{i=1}^{5}p_i=uT_P\sum_{i=1}^{5}q_i.$$
Ein Kandidat \(m\) ist also genau dann zulässig, wenn diese sechs ganzzahligen Gleichungen gleichzeitig mit \(p_i,q_i\ge 1\) lösbar sind.
Für das erste Produkt gelten \(P_1=5248\) und \(Q_1=640\). Daher
$$\frac{u}{v}=\frac{P_1q_1}{Q_1p_1}=\frac{5248\,q_1}{640\,p_1}=\frac{41q_1}{5p_1}.$$
Da \(1\le p_1\le P_1\) und \(1\le q_1\le Q_1\), muss jeder gültige Faktor unter den vollständig gekürzten Brüchen
$$m=\frac{41b}{5a},\qquad 1\le a\le 5248,\quad 1\le b\le 640,\quad m>1$$
auftreten. Das ist das entscheidende Endlichkeitsargument: Man muss keine beliebigen rationalen Zahlen erraten, sondern nur die durch Produkt 1 erzwungene endliche Kandidatenmenge erzeugen, sortieren und deduplizieren.
Die fünf Lieferantenquotienten sind nicht alle verschieden:
$$\frac{Q_1}{P_1}=\frac{5}{41},\qquad \frac{Q_2}{P_2}=\frac{Q_3}{P_3}=\frac{Q_5}{P_5}=\frac{59}{41},\qquad \frac{Q_4}{P_4}=\frac{59}{90}.$$
Damit zerfallen die Produkte natürlich in drei Gruppen:
$$G_0=\{1\},\qquad G_1=\{2,3,5\},\qquad G_2=\{4\}.$$
Für einen festen Kandidaten \(m=\frac{u}{v}\) sei der Grundquotient der Gruppe \(g\) gleich \(\frac{\beta_g}{\alpha_g}\), also einer der drei Werte \(\frac{5}{41}\), \(\frac{59}{41}\) oder \(\frac{59}{90}\). Reduziere
$$\frac{u\beta_g}{v\alpha_g}=\frac{n_g}{d_g}$$
auf vollständig gekürzte Form. Dann gilt für jedes Produkt \(i\in G_g\)
$$\frac{q_i}{p_i}=\frac{uQ_i}{vP_i}=\frac{n_g}{d_g},$$
also existiert eine positive ganze Zahl \(t_i\) mit
$$p_i=d_gt_i,\qquad q_i=n_gt_i.$$
Das ist die zentrale Vereinfachung: Sobald \(m\) feststeht, liefert jedes Produkt nur noch einen ganzzahligen Parameter \(t_i\), und Produkte mit gleichem Lieferantenquotienten teilen sich dasselbe Paar \((n_g,d_g)\).
Die gewählten Zahlen dürfen die Liefermengen nicht überschreiten. Für jedes Produkt \(i\in G_g\) gilt deshalb
$$1\le t_i\le \min\left(\left\lfloor\frac{P_i}{d_g}\right\rfloor,\left\lfloor\frac{Q_i}{n_g}\right\rfloor\right).$$
Nun definieren wir pro Gruppe nur noch eine Summe:
$$s_g=\sum_{i\in G_g}t_i.$$
Hat eine Gruppe \(|G_g|\) Produkte, dann ist der kleinste mögliche Wert
$$L_g=|G_g|,$$
weil jedes \(t_i\ge 1\) sein muss. Der größte mögliche Wert ist
$$H_g=\sum_{i\in G_g}\min\left(\left\lfloor\frac{P_i}{d_g}\right\rfloor,\left\lfloor\frac{Q_i}{n_g}\right\rfloor\right).$$
Wichtig ist, dass tatsächlich jede ganze Zahl zwischen \(L_g\) und \(H_g\) erreichbar ist. Es gibt hier kein verdecktes Teilmengenproblem: Alle \(t_i\) verändern sich in Schritten von 1. Ausgehend von der Minimalbelegung \(t_i=1\) kann man die Variablen nacheinander erhöhen, bis jede gewünschte Gruppensumme im Intervall getroffen wird.
Damit lassen sich die fünf ursprünglichen Parameter \(t_1,\dots,t_5\) durch die drei intervallbeschränkten Summen
$$s_0\in[L_0,H_0],\qquad s_1\in[L_1,H_1],\qquad s_2\in[L_2,H_2]$$
ersetzen, wobei \(L_0=1\), \(L_1=3\) und \(L_2=1\) gilt.
Setzt man \(p_i=d_gt_i\) und \(q_i=n_gt_i\) in die globale Bedingung ein, so erhält man
$$vT_Q\sum_{g=0}^{2}d_gs_g=uT_P\sum_{g=0}^{2}n_gs_g.$$
Bringt man alle Terme auf eine Seite und definiert
$$c_g=vT_Qd_g-uT_Pn_g,$$
dann ist \(m\) genau dann machbar, wenn es ganze Zahlen \(s_0,s_1,s_2\) in ihren Intervallen gibt mit
$$c_0s_0+c_1s_1+c_2s_2=0.$$
Die Implementierung fixiert \(s_0\) und schreibt das Problem als
$$c_1s_1+c_2s_2=r,\qquad r=-c_0s_0.$$
Wenn \(g=\gcd(c_1,c_2)\) den Wert \(r\) nicht teilt, gibt es keine Lösung. Andernfalls gilt: Ist
$$c_1x_0+c_2y_0=g,$$
dann haben alle Lösungen die Form
$$s_1=x_0\frac{r}{g}+\frac{c_2}{g}t,\qquad s_2=y_0\frac{r}{g}-\frac{c_1}{g}t,\qquad t\in\mathbb{Z}.$$
Danach bleibt nur noch Intervallarithmetik: Man schneidet den von \(L_1\le s_1\le H_1\) erzwungenen Bereich für \(t\) mit dem von \(L_2\le s_2\le H_2\) erzwungenen Bereich. Eine nichtleere Schnittmenge bedeutet, dass der Kandidat funktioniert.
Die Implementierungen finden schließlich als größten zulässigen Faktor
$$m=\frac{123}{59}.$$
Dafür sind die drei Gruppenreduktionen
$$\frac{123\cdot 5}{59\cdot 41}=\frac{15}{59},\qquad \frac{123\cdot 59}{59\cdot 41}=3=\frac{3}{1},\qquad \frac{123\cdot 59}{59\cdot 90}=\frac{41}{30}.$$
Somit lauten die Gruppenparameter
$$ (d_0,n_0)=(59,15),\qquad (d_1,n_1)=(1,3),\qquad (d_2,n_2)=(30,41). $$
Die zugehörigen oberen Schranken sind
$$H_0=\min\!\left(\left\lfloor\frac{5248}{59}\right\rfloor,\left\lfloor\frac{640}{15}\right\rfloor\right)=42,$$
$$H_1=\min\!\left(\left\lfloor\frac{1312}{1}\right\rfloor,\left\lfloor\frac{1888}{3}\right\rfloor\right)+\min\!\left(\left\lfloor\frac{2624}{1}\right\rfloor,\left\lfloor\frac{3776}{3}\right\rfloor\right)+\min\!\left(\left\lfloor\frac{3936}{1}\right\rfloor,\left\lfloor\frac{5664}{3}\right\rfloor\right)=629+1258+1888=3775,$$
$$H_2=\min\!\left(\left\lfloor\frac{5760}{30}\right\rfloor,\left\lfloor\frac{3776}{41}\right\rfloor\right)=92.$$
Die Koeffizienten werden zu
$$ (c_0,c_1,c_2)=(19971264,-6037824,-67344960)=464448\,(43,-13,-145). $$
Damit ist die Machbarkeit äquivalent zu
$$43s_0-13s_1-145s_2=0.$$
Eine gültige Wahl ist
$$ (s_0,s_1,s_2)=(7,12,1), $$
denn \(43\cdot 7-13\cdot 12-145\cdot 1=0\). Die mittlere Gruppensumme \(s_1=12\) lässt sich leicht realisieren, zum Beispiel mit den drei dortigen Produktparametern \(1,1,10\). Dieses konkrete Beispiel zeigt unmittelbar, warum \(\frac{123}{59}\) den Test besteht.
Die C++-, Python- und Java-Implementierungen folgen der Herleitung direkt. Sie enumerieren nie beliebige Fünfertupel von Produktzahlen, sondern durchsuchen die durch Produkt 1 erzwungene rationale Kandidatenmenge und testen jeden Kandidaten mit exakter Ganzzahlarithmetik.
Die Implementierung läuft über alle positiven Möglichkeiten für das erste Produkt, bildet den gekürzten Bruch \(\frac{41b}{5a}\), verwirft Kandidaten mit \(m\le 1\), sortiert die übrigen Brüche und entfernt Dubletten. Dadurch entsteht der vollständige endliche Suchraum.
Für einen festen Kandidaten \(m=\frac{u}{v}\) berechnet die Implementierung die drei gekürzten Gruppenquotienten \(\frac{n_g}{d_g}\), daraus die obere Schranke für jedes Produkt und das Intervall \([L_g,H_g]\) jeder Gruppensumme \(s_g\). Falls irgendein Produkt keinen positiven zulässigen Wert besitzt, wird der Kandidat sofort verworfen.
Andernfalls werden die Koeffizienten \(c_g=vT_Qd_g-uT_Pn_g\) gebildet. Danach iteriert die Implementierung über alle zulässigen \(s_0\) und prüft jeweils, ob die verbleibende Gleichung mit zwei Variablen innerhalb der Intervalle lösbar ist. Dieser Teil verwendet den erweiterten euklidischen Algorithmus und eine Intervallschrumpfung für den freien Parameter \(t\).
Jeder Kandidat kann unabhängig geprüft werden. Die C++- und Java-Implementierungen verteilen diese Prüfungen auf mehrere Threads; die Python-Implementierung führt dieselbe Mathematik seriell aus. Nach dem Einsammeln aller gültigen Kandidaten wird der größte gekürzte Bruch ausgegeben.
Die Kandidatenerzeugung startet mit den \(5248\cdot 640=3{,}358{,}720\) Rohbrüchen, die durch Produkt 1 erzwungen werden. Das Sortieren und Deduplizieren kostet \(O(M\log M)\) mit \(M=3{,}358{,}720\).
Für jeden unterschiedlichen Kandidaten ist die Gruppen-Vorverarbeitung konstant schnell, und die Hauptschleife läuft nur über die möglichen Werte von \(s_0\). Da die erste Gruppe aus nur einem Produkt besteht, umfasst dieser Bereich nie mehr als einige hundert Werte. Die zweidimensionale diophantische Prüfung ist nach Berechnung von ggT und Intervallen \(O(1)\). Praktisch wird die Laufzeit daher von der Kandidatenerzeugung und einer Machbarkeitsphase \(O(C\cdot R)\) dominiert, wobei \(C\) die Zahl der verschiedenen Kandidaten und \(R\) die Breite des Intervalls der ersten Gruppe ist. Der Speicherverbrauch beträgt \(O(C)\) für die Kandidatenliste plus konstanten Zusatzspeicher pro Test. Parallelisierung verbessert die Wandzeit, ändert aber nicht die asymptotischen Schranken.
Problem, iki tedarikçinin lüks hediye sepetleri için verilen beş ürün toplamını kullanır. Notasyonu sade tutmak için bu sayıları
$$P=(5248,1312,2624,5760,3936),\qquad Q=(640,1888,3776,3776,5664)$$
şeklinde yazalım. Genel toplamlar ise
$$T_P=18880,\qquad T_Q=15744$$
olur. Amaç, \(m>1\) olacak en büyük rasyonel sayıyı bulmaktır. Bunun için her ürün için pozitif tamsayı \(p_i\) ve \(q_i\) değerleri seçilebilmeli; aynı çarpan \(m\) hem ürün bazında hem de beş ürün birlikte toplandığında geçerli olmalıdır. Beş bağımsız sayı çifti üzerinden kaba kuvvet araması çok büyük olduğu için çözüm, verilen tedarik oranlarındaki yapıyı kullanır.
Aranan çarpanı sadeleşmiş biçimde \(m=\frac{u}{v}\) olarak yazalım. Uygulamalar problemi iki aşamada çözüyor: önce \(m\) için mümkün tüm rasyonel adayları üretiyor, sonra her adayın hem ürün kısıtlarını hem de toplam tutarlılık denklemini sağlayan pozitif tamsayılara izin verip vermediğini kesin aritmetik ile test ediyor.
Her ürün \(i\) için uygulama, şu koşulu sağlayan pozitif tamsayı \(p_i\) ve \(q_i\) değerleriyle çalışır:
$$vP_iq_i=uQ_ip_i.$$
Beş ürünün tamamı için toplu koşul ise
$$vT_Q\sum_{i=1}^{5}p_i=uT_P\sum_{i=1}^{5}q_i$$
şeklindedir. Dolayısıyla bir aday \(m\), ancak ve ancak bu altı tamsayı denklem eşzamanlı olarak \(p_i,q_i\ge 1\) şartıyla çözülebiliyorsa geçerlidir.
Birinci ürün için \(P_1=5248\) ve \(Q_1=640\) olduğundan
$$\frac{u}{v}=\frac{P_1q_1}{Q_1p_1}=\frac{5248\,q_1}{640\,p_1}=\frac{41q_1}{5p_1}$$
elde edilir. \(1\le p_1\le P_1\) ve \(1\le q_1\le Q_1\) olduğu için her geçerli çarpan, mutlaka şu sade kesirler arasında yer alır:
$$m=\frac{41b}{5a},\qquad 1\le a\le 5248,\quad 1\le b\le 640,\quad m>1.$$
Bu, problemin sonlu olmasını sağlayan temel gözlemdir. Rastgele rasyonel sayılar tahmin etmek yerine, yalnızca birinci ürünün zorunlu kıldığı sonlu aday kümesini üretmek, sıralamak ve tekilleştirmek yeterlidir.
Beş tedarik oranının hepsi farklı değildir:
$$\frac{Q_1}{P_1}=\frac{5}{41},\qquad \frac{Q_2}{P_2}=\frac{Q_3}{P_3}=\frac{Q_5}{P_5}=\frac{59}{41},\qquad \frac{Q_4}{P_4}=\frac{59}{90}.$$
Bu yüzden ürünler doğal olarak üç gruba ayrılır:
$$G_0=\{1\},\qquad G_1=\{2,3,5\},\qquad G_2=\{4\}.$$
Sabit bir \(m=\frac{u}{v}\) adayı için, grup \(g\)'nin temel oranını \(\frac{\beta_g}{\alpha_g}\) ile gösterelim; yani bu üç olası değer sırasıyla \(\frac{5}{41}\), \(\frac{59}{41}\) ve \(\frac{59}{90}\) olsun. O halde
$$\frac{u\beta_g}{v\alpha_g}=\frac{n_g}{d_g}$$
oranını sadeleştiririz. Böylece her \(i\in G_g\) için
$$\frac{q_i}{p_i}=\frac{uQ_i}{vP_i}=\frac{n_g}{d_g}$$
olur ve dolayısıyla bir pozitif tamsayı \(t_i\) vardır:
$$p_i=d_gt_i,\qquad q_i=n_gt_i.$$
Asıl sadeleşme burada olur: \(m\) sabitlenince her ürün yalnızca bir tamsayı parametre \(t_i\) katkısı yapar ve aynı tedarik oranını paylaşan ürünler aynı \((n_g,d_g)\) çiftini kullanır.
Seçilen sayılar verilen tedarik miktarlarını aşamaz. Bu nedenle her \(i\in G_g\) için
$$1\le t_i\le \min\left(\left\lfloor\frac{P_i}{d_g}\right\rfloor,\left\lfloor\frac{Q_i}{n_g}\right\rfloor\right)$$
olmalıdır. Şimdi her grup için tek bir toplam tanımlayalım:
$$s_g=\sum_{i\in G_g}t_i.$$
Bir grubun \(|G_g|\) adet ürünü varsa en küçük mümkün değer
$$L_g=|G_g|$$
olur; çünkü her \(t_i\ge 1\) olmalıdır. En büyük mümkün değer ise
$$H_g=\sum_{i\in G_g}\min\left(\left\lfloor\frac{P_i}{d_g}\right\rfloor,\left\lfloor\frac{Q_i}{n_g}\right\rfloor\right).$$
Buradaki önemli nokta şudur: \(L_g\) ile \(H_g\) arasındaki her tam sayı gerçekten elde edilebilir. Gizli bir alt küme toplamı problemi yoktur; çünkü tüm \(t_i\) değerleri 1 adımlarla değişir. En küçük atama \(t_i=1\) ile başlanıp değişkenler tek tek artırılarak aralıktaki her hedef toplama ulaşılabilir.
Böylece başlangıçtaki beş parametre \(t_1,\dots,t_5\), üç aralıklı grup toplamına indirgenir:
$$s_0\in[L_0,H_0],\qquad s_1\in[L_1,H_1],\qquad s_2\in[L_2,H_2],$$
burada \(L_0=1\), \(L_1=3\), \(L_2=1\) olur.
\(p_i=d_gt_i\) ve \(q_i=n_gt_i\) ifadelerini toplam koşuluna koyarsak
$$vT_Q\sum_{g=0}^{2}d_gs_g=uT_P\sum_{g=0}^{2}n_gs_g$$
elde edilir. Tüm terimleri bir tarafa toplayıp
$$c_g=vT_Qd_g-uT_Pn_g$$
tanımını yaparsak, \(m\) adayının geçerli olması için ve ancak için aralıklarda kalan tamsayı \(s_0,s_1,s_2\) değerleriyle
$$c_0s_0+c_1s_1+c_2s_2=0$$
eşitliği sağlanmalıdır. Uygulama \(s_0\)'ı sabitler ve problemi
$$c_1s_1+c_2s_2=r,\qquad r=-c_0s_0$$
şekline getirir. Eğer \(g=\gcd(c_1,c_2)\), \(r\)'yi bölmüyorsa çözüm yoktur. Aksi halde
$$c_1x_0+c_2y_0=g$$
olacak bir Bézout çözümü bulunduğunda tüm çözümler
$$s_1=x_0\frac{r}{g}+\frac{c_2}{g}t,\qquad s_2=y_0\frac{r}{g}-\frac{c_1}{g}t,\qquad t\in\mathbb{Z}$$
biçimindedir. Bundan sonra kalan tek iş aralık hesabıdır: \(L_1\le s_1\le H_1\) ile gelen \(t\) aralığı, \(L_2\le s_2\le H_2\) ile gelen aralıkla kesiştirilir. Kesişim boş değilse aday çalışır.
Uygulamalar sonunda en büyük geçerli çarpanın
$$m=\frac{123}{59}$$
olduğunu bulur. Bu değer için üç grup indirgemesi
$$\frac{123\cdot 5}{59\cdot 41}=\frac{15}{59},\qquad \frac{123\cdot 59}{59\cdot 41}=3=\frac{3}{1},\qquad \frac{123\cdot 59}{59\cdot 90}=\frac{41}{30}$$
şeklindedir. Dolayısıyla grup parametreleri
$$ (d_0,n_0)=(59,15),\qquad (d_1,n_1)=(1,3),\qquad (d_2,n_2)=(30,41) $$
olur. Buna karşılık üst sınırlar
$$H_0=\min\!\left(\left\lfloor\frac{5248}{59}\right\rfloor,\left\lfloor\frac{640}{15}\right\rfloor\right)=42,$$
$$H_1=\min\!\left(\left\lfloor\frac{1312}{1}\right\rfloor,\left\lfloor\frac{1888}{3}\right\rfloor\right)+\min\!\left(\left\lfloor\frac{2624}{1}\right\rfloor,\left\lfloor\frac{3776}{3}\right\rfloor\right)+\min\!\left(\left\lfloor\frac{3936}{1}\right\rfloor,\left\lfloor\frac{5664}{3}\right\rfloor\right)=629+1258+1888=3775,$$
$$H_2=\min\!\left(\left\lfloor\frac{5760}{30}\right\rfloor,\left\lfloor\frac{3776}{41}\right\rfloor\right)=92$$
olur. Katsayılar
$$ (c_0,c_1,c_2)=(19971264,-6037824,-67344960)=464448\,(43,-13,-145) $$
şeklinde sadeleşir. Yani uygunluk koşulu aslında
$$43s_0-13s_1-145s_2=0$$
demektir. Geçerli bir seçim
$$ (s_0,s_1,s_2)=(7,12,1) $$
olur; çünkü \(43\cdot 7-13\cdot 12-145\cdot 1=0\). Orta gruptaki \(s_1=12\) toplamı örneğin \(1,1,10\) dağılımıyla sağlanabilir. Bu somut yapı, \(\frac{123}{59}\) adayının neden testi geçtiğini açıkça gösterir.
C++, Python ve Java uygulamaları doğrudan bu türetmeyi uygular. Beş ürün için rastgele sayı beşlileri denemek yerine, birinci ürünün zorunlu kıldığı rasyonel aday kümesini üretir ve her adayı tam sayı aritmetiğiyle sınar.
Uygulama birinci ürün için tüm pozitif seçenekleri dolaşır, sadeleşmiş \(\frac{41b}{5a}\) kesrini oluşturur, \(m\le 1\) olanları eler, kalanları sıralar ve tekrarları siler. Böylece eksiksiz sonlu arama uzayı elde edilir.
Sabit bir \(m=\frac{u}{v}\) için uygulama önce üç grup oranını \(\frac{n_g}{d_g}\) biçiminde indirger, sonra her ürünün üst sınırını ve her grup toplamı için \([L_g,H_g]\) aralığını hesaplar. Eğer herhangi bir ürün için pozitif uygun değer kalmıyorsa aday hemen reddedilir.
Aksi halde \(c_g=vT_Qd_g-uT_Pn_g\) katsayıları kurulur. Sonra tüm uygun \(s_0\) değerleri üzerinden geçilir ve her biri için iki değişkenli kalan denklemin aralıklar içinde çözülebilir olup olmadığı sınanır. Bu adım genişletilmiş Öklid algoritması ve serbest parametre \(t\) için aralık daraltma kullanır.
Her aday birbirinden bağımsız test edilebilir. C++ ve Java uygulamaları bu kontrolleri çok iş parçacığına dağıtır; Python uygulaması aynı matematiği seri çalıştırır. Tüm geçerli adaylar toplandıktan sonra en büyük sade kesir sonuç olarak döndürülür.
Aday üretimi, birinci ürünün zorladığı \(5248\cdot 640=3{,}358{,}720\) ham kesir ile başlar. Bunları sıralayıp tekilleştirmenin maliyeti \(M=3{,}358{,}720\) için \(O(M\log M)\) olur.
Her farklı aday için grup ön işlemi sabit zamandır ve ana döngü yalnızca \(s_0\)'ın olası değerleri üzerinde çalışır. İlk grup tek bir üründen oluştuğu için bu aralık hiçbir zaman birkaç yüz değerden fazla olmaz. İki değişkenli Diofant denklemi testi, ggT ve parametre aralıkları bulunduktan sonra \(O(1)\)'dir. Pratikte çalışma süresi bu nedenle aday üretimi ile \(O(C\cdot R)\) biçimindeki uygunluk fazı tarafından belirlenir; burada \(C\) farklı aday sayısı, \(R\) ise ilk grubun aralık genişliğidir. Bellek kullanımı aday listesi için \(O(C)\), her test için ise sabit ek alandır. Paralellik duvar saati süresini düşürür ama asimptotik büyüklüğü değiştirmez.
El problema da los totales de cinco productos para dos proveedores de cestas de lujo. Para mantener la notación neutral, escribamos esos totales como
$$P=(5248,1312,2624,5760,3936),\qquad Q=(640,1888,3776,3776,5664).$$
Sus sumas globales son
$$T_P=18880,\qquad T_Q=15744.$$
Se busca el mayor número racional \(m>1\) para el cual sea posible escoger enteros positivos \(p_i\) y \(q_i\) en los cinco productos, de modo que el mismo sesgo multiplicativo \(m\) aparezca tanto producto por producto como después de agrupar los cinco productos. Una búsqueda bruta sobre cinco pares independientes sería enorme, así que la solución explota la estructura fija de los totales suministrados.
Escribamos el multiplicador buscado como \(m=\frac{u}{v}\) en forma reducida. Las implementaciones separan el problema en dos partes: primero generan todos los candidatos racionales posibles para \(m\); después comprueban exactamente cuáles admiten conteos enteros positivos que satisfacen al mismo tiempo las restricciones por producto y la ecuación global de consistencia.
Para cada producto \(i\), la implementación trabaja con enteros positivos \(p_i\) y \(q_i\) sujetos a
$$vP_iq_i=uQ_ip_i.$$
La condición combinada sobre los cinco productos es
$$vT_Q\sum_{i=1}^{5}p_i=uT_P\sum_{i=1}^{5}q_i.$$
Así, un candidato \(m\) es válido si y solo si estas seis ecuaciones enteras pueden satisfacerse simultáneamente con \(p_i,q_i\ge 1\).
Para el primer producto tenemos \(P_1=5248\) y \(Q_1=640\), luego
$$\frac{u}{v}=\frac{P_1q_1}{Q_1p_1}=\frac{5248\,q_1}{640\,p_1}=\frac{41q_1}{5p_1}.$$
Como \(1\le p_1\le P_1\) y \(1\le q_1\le Q_1\), todo multiplicador válido debe aparecer entre las fracciones reducidas
$$m=\frac{41b}{5a},\qquad 1\le a\le 5248,\quad 1\le b\le 640,\quad m>1.$$
Este es el argumento finito decisivo: no hace falta adivinar racionales arbitrarios. Basta enumerar, reducir, ordenar y eliminar duplicados de las fracciones forzadas por el primer producto.
Las cinco razones de suministro no son todas distintas:
$$\frac{Q_1}{P_1}=\frac{5}{41},\qquad \frac{Q_2}{P_2}=\frac{Q_3}{P_3}=\frac{Q_5}{P_5}=\frac{59}{41},\qquad \frac{Q_4}{P_4}=\frac{59}{90}.$$
Por tanto, los productos se dividen naturalmente en tres grupos:
$$G_0=\{1\},\qquad G_1=\{2,3,5\},\qquad G_2=\{4\}.$$
Para un candidato fijo \(m=\frac{u}{v}\), sea \(\frac{\beta_g}{\alpha_g}\) la razón base del grupo \(g\); es decir, uno de los tres valores \(\frac{5}{41}\), \(\frac{59}{41}\) o \(\frac{59}{90}\). Reducimos
$$\frac{u\beta_g}{v\alpha_g}=\frac{n_g}{d_g}.$$
Entonces, para cada producto \(i\in G_g\),
$$\frac{q_i}{p_i}=\frac{uQ_i}{vP_i}=\frac{n_g}{d_g},$$
de modo que existe un entero positivo \(t_i\) tal que
$$p_i=d_gt_i,\qquad q_i=n_gt_i.$$
Aquí ocurre la simplificación central: una vez fijado \(m\), cada producto aporta solo un parámetro entero \(t_i\), y los productos con la misma razón de suministro comparten el mismo par \((n_g,d_g)\).
Los conteos elegidos no pueden exceder los totales suministrados. Por eso, para cada \(i\in G_g\),
$$1\le t_i\le \min\left(\left\lfloor\frac{P_i}{d_g}\right\rfloor,\left\lfloor\frac{Q_i}{n_g}\right\rfloor\right).$$
Definimos ahora una única suma por grupo:
$$s_g=\sum_{i\in G_g}t_i.$$
Si un grupo contiene \(|G_g|\) productos, el menor valor posible es
$$L_g=|G_g|,$$
porque todo \(t_i\ge 1\). El mayor valor posible es
$$H_g=\sum_{i\in G_g}\min\left(\left\lfloor\frac{P_i}{d_g}\right\rfloor,\left\lfloor\frac{Q_i}{n_g}\right\rfloor\right).$$
La observación útil es que cualquier entero entre \(L_g\) y \(H_g\) es alcanzable. No aparece un problema oculto de subconjuntos: todos los \(t_i\) cambian de uno en uno. Partiendo de la asignación mínima \(t_i=1\), se pueden aumentar las variables una a una hasta obtener cualquier suma de grupo dentro del intervalo.
Así, los cinco parámetros originales \(t_1,\dots,t_5\) se sustituyen por las tres sumas acotadas
$$s_0\in[L_0,H_0],\qquad s_1\in[L_1,H_1],\qquad s_2\in[L_2,H_2],$$
con \(L_0=1\), \(L_1=3\) y \(L_2=1\).
Sustituyendo \(p_i=d_gt_i\) y \(q_i=n_gt_i\) en la condición global se obtiene
$$vT_Q\sum_{g=0}^{2}d_gs_g=uT_P\sum_{g=0}^{2}n_gs_g.$$
Llevando todo a un solo lado y definiendo
$$c_g=vT_Qd_g-uT_Pn_g,$$
vemos que \(m\) es factible si y solo si existen enteros \(s_0,s_1,s_2\) en sus intervalos tales que
$$c_0s_0+c_1s_1+c_2s_2=0.$$
La implementación fija \(s_0\) y reescribe el problema como
$$c_1s_1+c_2s_2=r,\qquad r=-c_0s_0.$$
Si \(g=\gcd(c_1,c_2)\) no divide a \(r\), no hay solución. Si sí lo divide y
$$c_1x_0+c_2y_0=g,$$
entonces todas las soluciones vienen dadas por
$$s_1=x_0\frac{r}{g}+\frac{c_2}{g}t,\qquad s_2=y_0\frac{r}{g}-\frac{c_1}{g}t,\qquad t\in\mathbb{Z}.$$
Lo que queda es aritmética de intervalos: se intersecta el rango de \(t\) impuesto por \(L_1\le s_1\le H_1\) con el rango impuesto por \(L_2\le s_2\le H_2\). Si la intersección no es vacía, el candidato funciona.
Las implementaciones terminan encontrando que el mayor multiplicador factible es
$$m=\frac{123}{59}.$$
Para este valor, las tres reducciones de grupo son
$$\frac{123\cdot 5}{59\cdot 41}=\frac{15}{59},\qquad \frac{123\cdot 59}{59\cdot 41}=3=\frac{3}{1},\qquad \frac{123\cdot 59}{59\cdot 90}=\frac{41}{30}.$$
Por tanto, los parámetros de grupo son
$$ (d_0,n_0)=(59,15),\qquad (d_1,n_1)=(1,3),\qquad (d_2,n_2)=(30,41). $$
Las cotas superiores correspondientes son
$$H_0=\min\!\left(\left\lfloor\frac{5248}{59}\right\rfloor,\left\lfloor\frac{640}{15}\right\rfloor\right)=42,$$
$$H_1=\min\!\left(\left\lfloor\frac{1312}{1}\right\rfloor,\left\lfloor\frac{1888}{3}\right\rfloor\right)+\min\!\left(\left\lfloor\frac{2624}{1}\right\rfloor,\left\lfloor\frac{3776}{3}\right\rfloor\right)+\min\!\left(\left\lfloor\frac{3936}{1}\right\rfloor,\left\lfloor\frac{5664}{3}\right\rfloor\right)=629+1258+1888=3775,$$
$$H_2=\min\!\left(\left\lfloor\frac{5760}{30}\right\rfloor,\left\lfloor\frac{3776}{41}\right\rfloor\right)=92.$$
Los coeficientes pasan a ser
$$ (c_0,c_1,c_2)=(19971264,-6037824,-67344960)=464448\,(43,-13,-145). $$
Así, la factibilidad equivale a
$$43s_0-13s_1-145s_2=0.$$
Una elección válida es
$$ (s_0,s_1,s_2)=(7,12,1), $$
porque \(43\cdot 7-13\cdot 12-145\cdot 1=0\). La suma intermedia \(s_1=12\) se puede realizar, por ejemplo, con parámetros \(1,1,10\) en ese grupo. Este ejemplo concreto deja claro por qué \(\frac{123}{59}\) supera la prueba.
Las implementaciones en C++, Python y Java siguen exactamente esta derivación. Nunca enumeran quíntuplas arbitrarias de conteos. En su lugar, recorren el conjunto de candidatos racionales forzado por el primer producto y prueban cada candidato con aritmética entera exacta.
La implementación recorre todos los conteos positivos posibles del primer producto, forma la fracción reducida \(\frac{41b}{5a}\), descarta los candidatos con \(m\le 1\), ordena las fracciones restantes y elimina duplicados. Con ello construye el espacio de búsqueda completo y finito.
Para un candidato fijo \(m=\frac{u}{v}\), la implementación calcula las tres razones reducidas \(\frac{n_g}{d_g}\), luego las cotas superiores producto a producto y el intervalo \([L_g,H_g]\) de cada suma \(s_g\). Si algún producto no admite un valor positivo, el candidato se rechaza de inmediato.
Si supera ese filtro, se forman los coeficientes \(c_g=vT_Qd_g-uT_Pn_g\). Después se recorre todo \(s_0\) admisible y, para cada caso, se comprueba si la ecuación restante en dos variables tiene solución dentro de los intervalos. Esa comprobación usa el algoritmo de Euclides extendido y el recorte de intervalos del parámetro libre \(t\).
Cada candidato se puede comprobar de forma independiente. Las implementaciones en C++ y Java reparten esas comprobaciones entre varios hilos; la de Python realiza el mismo cálculo en serie. Tras reunir todos los candidatos factibles, se devuelve la fracción reducida más grande.
La generación de candidatos arranca con las \(5248\cdot 640=3{,}358{,}720\) fracciones brutas forzadas por el primer producto. Ordenarlas y deduplicarlas cuesta \(O(M\log M)\) con \(M=3{,}358{,}720\).
Para cada candidato distinto, el preprocesamiento por grupos es constante, y el bucle principal solo recorre los valores posibles de \(s_0\). Como el primer grupo contiene un solo producto, ese rango nunca tiene más que unos pocos cientos de valores. La comprobación diofántica en dos variables es \(O(1)\) una vez calculados el gcd y los intervalos del parámetro. En la práctica, el tiempo total está dominado por la enumeración de candidatos y una fase de factibilidad \(O(C\cdot R)\), donde \(C\) es el número de candidatos distintos y \(R\) es la anchura del intervalo del primer grupo. La memoria es \(O(C)\) para almacenar la lista de candidatos, más estado auxiliar constante por prueba. El paralelismo reduce el tiempo de pared, pero no cambia el orden asintótico.
题目给出两家供应方在五种豪华礼篮商品上的总数量。为了让推导更清晰，记这两列数据为
$$P=(5248,1312,2624,5760,3936),\qquad Q=(640,1888,3776,3776,5664).$$
它们的总和分别是
$$T_P=18880,\qquad T_Q=15744.$$
要求找到最大的有理数 \(m>1\)，使得对于五种商品，都能选出正整数 \(p_i\) 和 \(q_i\)，并且同一个乘法因子 \(m\) 既能在单个商品层面成立，也能在把五种商品合并之后成立。直接枚举五对独立整数的组合规模太大，因此真正的解法必须利用这组固定供货总数里隐藏的比例结构。
把目标倍率写成最简分数 \(m=\frac{u}{v}\)。三份实现都遵循同一条思路：先构造出所有可能的有理数候选，再对每个候选做一次严格的整数可行性判定，检查它是否同时满足逐商品约束和整体约束。
对每个商品 \(i\)，实现里都引入正整数 \(p_i\) 与 \(q_i\)，要求它们满足
$$vP_iq_i=uQ_ip_i.$$
把五种商品合并后，还必须满足
$$vT_Q\sum_{i=1}^{5}p_i=uT_P\sum_{i=1}^{5}q_i.$$
因此，一个候选 \(m\) 是否有效，完全等价于这六个整数方程能否在 \(p_i,q_i\ge 1\) 的条件下同时成立。
对第 1 种商品，有 \(P_1=5248\)、\(Q_1=640\)，于是
$$\frac{u}{v}=\frac{P_1q_1}{Q_1p_1}=\frac{5248\,q_1}{640\,p_1}=\frac{41q_1}{5p_1}.$$
因为 \(1\le p_1\le P_1\) 且 \(1\le q_1\le Q_1\)，任何真正可行的倍率都一定出现在下面这批最简分数之中：
$$m=\frac{41b}{5a},\qquad 1\le a\le 5248,\quad 1\le b\le 640,\quad m>1.$$
这一步给出了整个搜索空间的有限性。实现并不需要在所有有理数里盲猜，只需要把第 1 种商品强制出来的分数全部枚举、约分、排序、去重即可。
题目的五个供货比例并不都不同：
$$\frac{Q_1}{P_1}=\frac{5}{41},\qquad \frac{Q_2}{P_2}=\frac{Q_3}{P_3}=\frac{Q_5}{P_5}=\frac{59}{41},\qquad \frac{Q_4}{P_4}=\frac{59}{90}.$$
于是商品自然分成三个组：
$$G_0=\{1\},\qquad G_1=\{2,3,5\},\qquad G_2=\{4\}.$$
对固定的候选 \(m=\frac{u}{v}\)，设第 \(g\) 组的基础比例为 \(\frac{\beta_g}{\alpha_g}\)，也就是三种可能的值 \(\frac{5}{41}\)、\(\frac{59}{41}\)、\(\frac{59}{90}\)。把
$$\frac{u\beta_g}{v\alpha_g}=\frac{n_g}{d_g}$$
约成最简分数。这样一来，对每个属于该组的商品 \(i\in G_g\)，都有
$$\frac{q_i}{p_i}=\frac{uQ_i}{vP_i}=\frac{n_g}{d_g},$$
因此必定存在一个正整数 \(t_i\)，使得
$$p_i=d_gt_i,\qquad q_i=n_gt_i.$$
这一步是整个问题的核心简化。也就是说，一旦 \(m\) 固定，每个商品只剩下一个整数参数 \(t_i\)；而且同一比例组中的商品共享同一个 \((n_g,d_g)\)。
选出的数量不能超过题目给出的总量，所以对每个 \(i\in G_g\)，都有
$$1\le t_i\le \min\left(\left\lfloor\frac{P_i}{d_g}\right\rfloor,\left\lfloor\frac{Q_i}{n_g}\right\rfloor\right).$$
现在对每一组只保留一个总和：
$$s_g=\sum_{i\in G_g}t_i.$$
如果该组有 \(|G_g|\) 个商品，那么最小值显然是
$$L_g=|G_g|,$$
因为每个 \(t_i\) 至少为 1。最大值则是
$$H_g=\sum_{i\in G_g}\min\left(\left\lfloor\frac{P_i}{d_g}\right\rfloor,\left\lfloor\frac{Q_i}{n_g}\right\rfloor\right).$$
这里有一个很关键、也是代码能够进一步压缩状态的原因：区间 \([L_g,H_g]\) 中的每个整数都能实现。因为所有 \(t_i\) 都是以步长 1 变化的，从最小配置 \(t_i=1\) 出发，只要逐个增加某些变量，就能达到区间内任何目标和。换句话说，这里不会出现隐藏的子集和障碍。
因此，原本的五个参数 \(t_1,\dots,t_5\) 可以被三个带区间约束的组和完全取代：
$$s_0\in[L_0,H_0],\qquad s_1\in[L_1,H_1],\qquad s_2\in[L_2,H_2],$$
其中 \(L_0=1\)、\(L_1=3\)、\(L_2=1\)。
把 \(p_i=d_gt_i\)、\(q_i=n_gt_i\) 代入整体条件，得到
$$vT_Q\sum_{g=0}^{2}d_gs_g=uT_P\sum_{g=0}^{2}n_gs_g.$$
把所有项移到一边，并定义
$$c_g=vT_Qd_g-uT_Pn_g,$$
就得到：候选 \(m\) 可行，当且仅当存在落在区间内的整数 \(s_0,s_1,s_2\)，满足
$$c_0s_0+c_1s_1+c_2s_2=0.$$
实现会固定 \(s_0\)，把问题改写为
$$c_1s_1+c_2s_2=r,\qquad r=-c_0s_0.$$
若 \(g=\gcd(c_1,c_2)\) 不能整除 \(r\)，则无解。若可以整除，并且已知
$$c_1x_0+c_2y_0=g,$$
那么所有整数解都可写成
$$s_1=x_0\frac{r}{g}+\frac{c_2}{g}t,\qquad s_2=y_0\frac{r}{g}-\frac{c_1}{g}t,\qquad t\in\mathbb{Z}.$$
于是最后只剩下区间求交：先由 \(L_1\le s_1\le H_1\) 得到 \(t\) 的允许范围，再由 \(L_2\le s_2\le H_2\) 得到另一个范围。如果两者交集非空，那么这个候选就是可行的。
三份实现最终找到的最大可行倍率是
$$m=\frac{123}{59}.$$
对这个候选，三组约分结果分别是
$$\frac{123\cdot 5}{59\cdot 41}=\frac{15}{59},\qquad \frac{123\cdot 59}{59\cdot 41}=3=\frac{3}{1},\qquad \frac{123\cdot 59}{59\cdot 90}=\frac{41}{30}.$$
因此三组参数为
$$ (d_0,n_0)=(59,15),\qquad (d_1,n_1)=(1,3),\qquad (d_2,n_2)=(30,41). $$
相应的上界是
$$H_0=\min\!\left(\left\lfloor\frac{5248}{59}\right\rfloor,\left\lfloor\frac{640}{15}\right\rfloor\right)=42,$$
$$H_1=\min\!\left(\left\lfloor\frac{1312}{1}\right\rfloor,\left\lfloor\frac{1888}{3}\right\rfloor\right)+\min\!\left(\left\lfloor\frac{2624}{1}\right\rfloor,\left\lfloor\frac{3776}{3}\right\rfloor\right)+\min\!\left(\left\lfloor\frac{3936}{1}\right\rfloor,\left\lfloor\frac{5664}{3}\right\rfloor\right)=629+1258+1888=3775,$$
$$H_2=\min\!\left(\left\lfloor\frac{5760}{30}\right\rfloor,\left\lfloor\frac{3776}{41}\right\rfloor\right)=92.$$
此时系数化为
$$ (c_0,c_1,c_2)=(19971264,-6037824,-67344960)=464448\,(43,-13,-145). $$
所以可行性条件等价于
$$43s_0-13s_1-145s_2=0.$$
一个可行解是
$$ (s_0,s_1,s_2)=(7,12,1), $$
因为 \(43\cdot 7-13\cdot 12-145\cdot 1=0\)。中间那一组的 \(s_1=12\) 也很容易具体实现，例如把该组三个商品的参数取成 \(1,1,10\)。这个例子清楚展示了为什么 \(\frac{123}{59}\) 会通过判定。
C++、Python 和 Java 三份实现都严格按照上面的推导来写。它们不会去枚举任意的五元整数配置，而是先构造由第 1 种商品强制出来的有理数候选集合，再用精确整数运算逐个判定。
实现遍历第 1 种商品的所有正整数可能值，形成约分后的 \(\frac{41b}{5a}\)，去掉 \(m\le 1\) 的情况，然后把剩余候选排序并去重。这样得到的就是完整、有限的搜索空间。
对固定的 \(m=\frac{u}{v}\)，实现先计算三组约分后的 \(\frac{n_g}{d_g}\)，再计算每个商品的上界以及每个组和 \(s_g\) 的区间 \([L_g,H_g]\)。如果某个商品连一个正整数可选值都没有，这个候选会立刻被否决。
若通过这一步，就构造系数 \(c_g=vT_Qd_g-uT_Pn_g\)，随后枚举所有可能的 \(s_0\)，并对每个 \(s_0\) 检查剩下的二元方程是否能在区间内求解。这一步使用扩展欧几里得算法，并对自由参数 \(t\) 做区间收缩。
每个候选都可以独立测试。C++ 和 Java 实现把这些测试分发到多个线程；Python 实现则串行执行相同的数学过程。所有可行候选收集完之后，取其中最大的最简分数作为结果。
候选生成从第 1 种商品强制出的 \(5248\cdot 640=3{,}358{,}720\) 个原始分数开始。对这批分数排序并去重需要 \(O(M\log M)\) 时间，其中 \(M=3{,}358{,}720\)。
对每个不同候选来说，分组预处理是常数时间，主循环只扫描 \(s_0\) 的可能取值。由于第一组只有一个商品，这个范围始终只有几百级别。二元丢番图判定在 gcd 和参数区间算出之后是 \(O(1)\)。因此实际运行时间主要由候选生成以及一个 \(O(C\cdot R)\) 的可行性阶段组成，其中 \(C\) 是不同候选的数量，\(R\) 是第一组区间的宽度。空间复杂度是保存候选列表所需的 \(O(C)\)，外加每次测试的常数级辅助状态。并行化只改善实际耗时，不改变渐近复杂度。
В задаче даны суммарные количества пяти видов товаров у двух поставщиков роскошных наборов. Чтобы не привязываться к именам столбцов, обозначим эти наборы чисел так:
$$P=(5248,1312,2624,5760,3936),\qquad Q=(640,1888,3776,3776,5664).$$
Их общие суммы равны
$$T_P=18880,\qquad T_Q=15744.$$
Нужно найти наибольшее рациональное число \(m>1\), для которого можно выбрать положительные целые числа \(p_i\) и \(q_i\) для всех пяти товаров так, чтобы один и тот же множитель \(m\) выполнялся и по каждому товару отдельно, и после объединения всех пяти товаров. Полный перебор пяти независимых пар был бы слишком велик, поэтому решение использует специальную структуру заданных отношений между поставками.
Запишем искомый множитель в несократимом виде \(m=\frac{u}{v}\). Все реализации делают одно и то же: сначала строят полный конечный список рациональных кандидатов, а затем для каждого кандидата проверяют, существуют ли положительные целые значения, удовлетворяющие и покомпонентным ограничениям, и общей уравновешивающей формуле.
Для каждого товара \(i\) вводятся положительные целые \(p_i\) и \(q_i\), связанные уравнением
$$vP_iq_i=uQ_ip_i.$$
После суммирования по всем пяти товарам требуется также
$$vT_Q\sum_{i=1}^{5}p_i=uT_P\sum_{i=1}^{5}q_i.$$
Следовательно, кандидат \(m\) допустим тогда и только тогда, когда эти шесть целочисленных уравнений имеют совместное решение при \(p_i,q_i\ge 1\).
Для первого товара \(P_1=5248\) и \(Q_1=640\), поэтому
$$\frac{u}{v}=\frac{P_1q_1}{Q_1p_1}=\frac{5248\,q_1}{640\,p_1}=\frac{41q_1}{5p_1}.$$
Так как \(1\le p_1\le P_1\) и \(1\le q_1\le Q_1\), любой допустимый множитель обязан встретиться среди сокращённых дробей
$$m=\frac{41b}{5a},\qquad 1\le a\le 5248,\quad 1\le b\le 640,\quad m>1.$$
Это и есть главный аргумент конечности. Реализация не ищет произвольные рациональные числа, а перебирает только те, которые неизбежно возникают из первого товара, затем сокращает, сортирует и убирает повторы.
Отношения поставок для пяти товаров принимают лишь три разных значения:
$$\frac{Q_1}{P_1}=\frac{5}{41},\qquad \frac{Q_2}{P_2}=\frac{Q_3}{P_3}=\frac{Q_5}{P_5}=\frac{59}{41},\qquad \frac{Q_4}{P_4}=\frac{59}{90}.$$
Поэтому товары естественно разбиваются на три группы:
$$G_0=\{1\},\qquad G_1=\{2,3,5\},\qquad G_2=\{4\}.$$
Для фиксированного кандидата \(m=\frac{u}{v}\) обозначим базовое отношение группы \(g\) через \(\frac{\beta_g}{\alpha_g}\), то есть это одно из значений \(\frac{5}{41}\), \(\frac{59}{41}\) или \(\frac{59}{90}\). Сократим дробь
$$\frac{u\beta_g}{v\alpha_g}=\frac{n_g}{d_g}.$$
Тогда для любого товара \(i\in G_g\)
$$\frac{q_i}{p_i}=\frac{uQ_i}{vP_i}=\frac{n_g}{d_g},$$
а значит существует положительное целое \(t_i\), такое что
$$p_i=d_gt_i,\qquad q_i=n_gt_i.$$
Именно здесь возникает решающее упрощение: после фиксации \(m\) каждый товар добавляет только один целочисленный параметр \(t_i\), а товары с одинаковым отношением поставок используют один и тот же набор \((n_g,d_g)\).
Выбранные количества не могут превышать исходные поставки, поэтому для каждого \(i\in G_g\)
$$1\le t_i\le \min\left(\left\lfloor\frac{P_i}{d_g}\right\rfloor,\left\lfloor\frac{Q_i}{n_g}\right\rfloor\right).$$
Теперь введём по одной сумме на группу:
$$s_g=\sum_{i\in G_g}t_i.$$
Если в группе \(|G_g|\) товаров, то минимально возможное значение равно
$$L_g=|G_g|,$$
потому что каждый \(t_i\ge 1\). Максимум равен
$$H_g=\sum_{i\in G_g}\min\left(\left\lfloor\frac{P_i}{d_g}\right\rfloor,\left\lfloor\frac{Q_i}{n_g}\right\rfloor\right).$$
Очень важно, что достижимы все целые числа между \(L_g\) и \(H_g\). Здесь не возникает скрытой задачи о подмножестве: все \(t_i\) меняются с шагом 1, поэтому, начиная с минимального выбора \(t_i=1\), можно поочерёдно увеличивать переменные и получить любую промежуточную сумму группы.
Значит, пять исходных параметров \(t_1,\dots,t_5\) можно заменить тремя интервалами
$$s_0\in[L_0,H_0],\qquad s_1\in[L_1,H_1],\qquad s_2\in[L_2,H_2],$$
где \(L_0=1\), \(L_1=3\), \(L_2=1\).
Подставляя \(p_i=d_gt_i\) и \(q_i=n_gt_i\) в глобальное условие, получаем
$$vT_Q\sum_{g=0}^{2}d_gs_g=uT_P\sum_{g=0}^{2}n_gs_g.$$
Переносим всё влево и определяем
$$c_g=vT_Qd_g-uT_Pn_g.$$
Тогда кандидат \(m\) допустим тогда и только тогда, когда существуют целые \(s_0,s_1,s_2\) в своих интервалах, удовлетворяющие
$$c_0s_0+c_1s_1+c_2s_2=0.$$
Реализация фиксирует \(s_0\) и переписывает задачу в виде
$$c_1s_1+c_2s_2=r,\qquad r=-c_0s_0.$$
Если \(g=\gcd(c_1,c_2)\) не делит \(r\), решений нет. Если делит и известно, что
$$c_1x_0+c_2y_0=g,$$
то все решения имеют вид
$$s_1=x_0\frac{r}{g}+\frac{c_2}{g}t,\qquad s_2=y_0\frac{r}{g}-\frac{c_1}{g}t,\qquad t\in\mathbb{Z}.$$
Остаётся чистая интервальная арифметика: пересечь допустимый диапазон параметра \(t\), вытекающий из \(L_1\le s_1\le H_1\), с диапазоном из \(L_2\le s_2\le H_2\). Непустое пересечение означает, что кандидат работает.
Все реализации в итоге находят, что максимальный допустимый множитель равен
$$m=\frac{123}{59}.$$
Для него три групповые редукции таковы:
$$\frac{123\cdot 5}{59\cdot 41}=\frac{15}{59},\qquad \frac{123\cdot 59}{59\cdot 41}=3=\frac{3}{1},\qquad \frac{123\cdot 59}{59\cdot 90}=\frac{41}{30}.$$
Значит, параметры групп равны
$$ (d_0,n_0)=(59,15),\qquad (d_1,n_1)=(1,3),\qquad (d_2,n_2)=(30,41). $$
Соответствующие верхние границы равны
$$H_0=\min\!\left(\left\lfloor\frac{5248}{59}\right\rfloor,\left\lfloor\frac{640}{15}\right\rfloor\right)=42,$$
$$H_1=\min\!\left(\left\lfloor\frac{1312}{1}\right\rfloor,\left\lfloor\frac{1888}{3}\right\rfloor\right)+\min\!\left(\left\lfloor\frac{2624}{1}\right\rfloor,\left\lfloor\frac{3776}{3}\right\rfloor\right)+\min\!\left(\left\lfloor\frac{3936}{1}\right\rfloor,\left\lfloor\frac{5664}{3}\right\rfloor\right)=629+1258+1888=3775,$$
$$H_2=\min\!\left(\left\lfloor\frac{5760}{30}\right\rfloor,\left\lfloor\frac{3776}{41}\right\rfloor\right)=92.$$
Коэффициенты становятся
$$ (c_0,c_1,c_2)=(19971264,-6037824,-67344960)=464448\,(43,-13,-145). $$
Следовательно, условие допустимости равносильно уравнению
$$43s_0-13s_1-145s_2=0.$$
Один допустимый выбор таков:
$$ (s_0,s_1,s_2)=(7,12,1), $$
потому что \(43\cdot 7-13\cdot 12-145\cdot 1=0\). Сумму \(s_1=12\) в средней группе легко реализовать, например распределением \(1,1,10\) между тремя товарами группы. Этот пример наглядно показывает, почему \(\frac{123}{59}\) проходит проверку.
Реализации на C++, Python и Java буквально следуют описанному выводу. Они не перебирают произвольные пятёрки значений, а строят множество рациональных кандидатов, вынужденное первым товаром, и проверяют каждый кандидат точной целочисленной арифметикой.
Реализация проходит по всем положительным вариантам для первого товара, формирует сокращённую дробь \(\frac{41b}{5a}\), отбрасывает случаи с \(m\le 1\), сортирует оставшиеся дроби и удаляет повторы. Так строится полный конечный поиск.
Для фиксированного \(m=\frac{u}{v}\) вычисляются три сокращённых групповых отношения \(\frac{n_g}{d_g}\), затем верхние границы по каждому товару и интервалы \([L_g,H_g]\) для сумм \(s_g\). Если для какого-то товара не остаётся ни одного положительного допустимого значения, кандидат сразу отвергается.
В противном случае строятся коэффициенты \(c_g=vT_Qd_g-uT_Pn_g\), затем перебираются все возможные \(s_0\), и для каждого из них проверяется, имеет ли оставшееся двухпеременное уравнение решение в заданных интервалах. Для этого используются расширенный алгоритм Евклида и ужатие диапазона свободного параметра \(t\).
Каждый кандидат проверяется независимо. Реализации на C++ и Java распределяют эти проверки по нескольким потокам; реализация на Python делает ту же математику последовательно. После сбора всех допустимых кандидатов выбирается максимальная сокращённая дробь.
Построение кандидатов начинается с \(5248\cdot 640=3{,}358{,}720\) сырых дробей, порождённых первым товаром. Их сортировка и удаление повторов требуют \(O(M\log M)\) времени при \(M=3{,}358{,}720\).
Для каждого различного кандидата групповая предобработка занимает константное время, а основной цикл перебирает только возможные значения \(s_0\). Поскольку первая группа содержит всего один товар, этот диапазон никогда не становится больше нескольких сотен значений. Двухпеременная диофантова проверка после вычисления gcd и интервалов параметра выполняется за \(O(1)\). Поэтому практически всё время уходит на построение кандидатов и фазу проверки вида \(O(C\cdot R)\), где \(C\) — число различных кандидатов, а \(R\) — ширина интервала первой группы. Память составляет \(O(C)\) для списка кандидатов плюс константное вспомогательное состояние на одну проверку. Параллельность уменьшает реальное время работы, но не меняет асимптотический порядок.
تعطي المسألة كميات خمسة أصناف من منتجات سلال الرفاهية عند موردين مختلفين. ولتجنّب الالتباس في الرموز، سنكتب هذين العمودين على الصورة
$$P=(5248,1312,2624,5760,3936),\qquad Q=(640,1888,3776,3776,5664).$$
ومجموعاهما الكليان هما
$$T_P=18880,\qquad T_Q=15744.$$
المطلوب إيجاد أكبر عدد نسبي \(m>1\) بحيث يمكن اختيار أعداد صحيحة موجبة \(p_i\) و\(q_i\) لكل صنف من الأصناف الخمسة، على أن يحقق العامل الضربي نفسه \(m\) العلاقة المطلوبة على مستوى كل صنف منفردًا وعلى مستوى الأصناف الخمسة مجتمعة. البحث المباشر في خمس أزواج مستقلة من الأعداد سيكون ضخمًا جدًا، لذلك يعتمد الحل على البنية الخاصة للنسب الثابتة في جداول الكميات المعطاة.
لنكتب العامل المطلوب في أبسط صورة على شكل \(m=\frac{u}{v}\). تتبع التطبيقات الثلاثة الفكرة نفسها: أولًا توليد جميع القيم النسبية الممكنة لـ \(m\)، ثم فحص كل مرشح فحصًا عدديًا دقيقًا لمعرفة هل توجد أعداد صحيحة موجبة تحقق قيود كل صنف وشرط الاتساق الكلي في الوقت نفسه.
لكل صنف \(i\)، تعمل الخوارزمية على عددين صحيحين موجبين \(p_i\) و\(q_i\) يحققان
$$vP_iq_i=uQ_ip_i.$$
أما الشرط المجمّع على الأصناف الخمسة فهو
$$vT_Q\sum_{i=1}^{5}p_i=uT_P\sum_{i=1}^{5}q_i.$$
إذن يكون المرشح \(m\) صالحًا إذا وفقط إذا أمكن حل هذه المعادلات الصحيحة الست مع الشرط \(p_i,q_i\ge 1\).
بالنسبة إلى الصنف الأول لدينا \(P_1=5248\) و\(Q_1=640\)، ومن ثم
$$\frac{u}{v}=\frac{P_1q_1}{Q_1p_1}=\frac{5248\,q_1}{640\,p_1}=\frac{41q_1}{5p_1}.$$
وبما أن \(1\le p_1\le P_1\) و\(1\le q_1\le Q_1\)، فإن أي قيمة صحيحة للمضاعف لا بد أن تظهر بين الكسور المختزلة
$$m=\frac{41b}{5a},\qquad 1\le a\le 5248,\quad 1\le b\le 640,\quad m>1.$$
هذه هي الحجة الأساسية التي تجعل فضاء البحث منتهيًا. فلا حاجة إلى تخمين كسور نسبية عامة، بل يكفي تعداد الكسور التي يفرضها الصنف الأول ثم اختزالها وترتيبها وإزالة التكرار منها.
النسب بين عمودي الإمداد ليست كلها مختلفة:
$$\frac{Q_1}{P_1}=\frac{5}{41},\qquad \frac{Q_2}{P_2}=\frac{Q_3}{P_3}=\frac{Q_5}{P_5}=\frac{59}{41},\qquad \frac{Q_4}{P_4}=\frac{59}{90}.$$
ولذلك تنقسم الأصناف طبيعيًا إلى ثلاث مجموعات:
$$G_0=\{1\},\qquad G_1=\{2,3,5\},\qquad G_2=\{4\}.$$
لأي مرشح ثابت \(m=\frac{u}{v}\)، لنرمز إلى النسبة الأساسية للمجموعة \(g\) بالرمز \(\frac{\beta_g}{\alpha_g}\)، أي إحدى القيم الثلاث \(\frac{5}{41}\) أو \(\frac{59}{41}\) أو \(\frac{59}{90}\). نختزل
$$\frac{u\beta_g}{v\alpha_g}=\frac{n_g}{d_g}.$$
عندئذٍ، لكل صنف \(i\in G_g\) نحصل على
$$\frac{q_i}{p_i}=\frac{uQ_i}{vP_i}=\frac{n_g}{d_g},$$
ومن ثم يوجد عدد صحيح موجب \(t_i\) بحيث
$$p_i=d_gt_i,\qquad q_i=n_gt_i.$$
هنا تظهر النقلة الأساسية في التبسيط: بعد تثبيت \(m\)، لا يضيف كل صنف إلا معاملًا صحيحًا واحدًا \(t_i\)، كما أن الأصناف التي تشترك في نسبة الإمداد نفسها تشترك أيضًا في الزوج نفسه \((n_g,d_g)\).
لا يمكن أن تتجاوز الكميات المختارة الأعداد المعطاة في الجدول، لذا لكل \(i\in G_g\) يجب أن يكون
$$1\le t_i\le \min\left(\left\lfloor\frac{P_i}{d_g}\right\rfloor,\left\lfloor\frac{Q_i}{n_g}\right\rfloor\right).$$
والآن نعرّف مجموعًا واحدًا لكل مجموعة:
$$s_g=\sum_{i\in G_g}t_i.$$
إذا كانت المجموعة تحتوي \(|G_g|\) أصنافًا، فإن أصغر قيمة ممكنة هي
$$L_g=|G_g|,$$
لأن كل \(t_i\) يجب أن يكون على الأقل 1. أما أكبر قيمة ممكنة فهي
$$H_g=\sum_{i\in G_g}\min\left(\left\lfloor\frac{P_i}{d_g}\right\rfloor,\left\lfloor\frac{Q_i}{n_g}\right\rfloor\right).$$
والفكرة المهمة هنا أن كل عدد صحيح بين \(L_g\) و\(H_g\) قابل للتحقيق بالفعل. لا توجد هنا صعوبة خفية من نوع مسألة مجموعات جزئية، لأن جميع المتغيرات \(t_i\) تتحرك بخطوة مقدارها 1. فإذا بدأنا من الوضع الأدنى \(t_i=1\)، أمكن زيادة المتغيرات واحدًا واحدًا حتى نصل إلى أي مجموع هدف داخل المجال.
وهكذا يمكن استبدال المعاملات الخمسة الأصلية \(t_1,\dots,t_5\) بثلاثة مجالات فقط:
$$s_0\in[L_0,H_0],\qquad s_1\in[L_1,H_1],\qquad s_2\in[L_2,H_2],$$
حيث \(L_0=1\) و\(L_1=3\) و\(L_2=1\).
بالتعويض عن \(p_i=d_gt_i\) و\(q_i=n_gt_i\) في الشرط الكلي نحصل على
$$vT_Q\sum_{g=0}^{2}d_gs_g=uT_P\sum_{g=0}^{2}n_gs_g.$$
ننقل جميع الحدود إلى طرف واحد ونعرف
$$c_g=vT_Qd_g-uT_Pn_g.$$
عندئذٍ يكون المرشح \(m\) ممكنًا إذا وفقط إذا وجدت أعداد صحيحة \(s_0,s_1,s_2\) داخل مجالاتها تحقق
$$c_0s_0+c_1s_1+c_2s_2=0.$$
تثبّت الخوارزمية القيمة \(s_0\) ثم تعيد كتابة المسألة على الصورة
$$c_1s_1+c_2s_2=r,\qquad r=-c_0s_0.$$
إذا كان \(g=\gcd(c_1,c_2)\) لا يقسم \(r\)، فلا يوجد حل. وإذا كان يقسمه، وكان
$$c_1x_0+c_2y_0=g,$$
فإن جميع الحلول تعطى بالصيغة
$$s_1=x_0\frac{r}{g}+\frac{c_2}{g}t,\qquad s_2=y_0\frac{r}{g}-\frac{c_1}{g}t,\qquad t\in\mathbb{Z}.$$
بعد ذلك لا يبقى إلا حساب مجالات: نأخذ المجال الذي يفرضه الشرط \(L_1\le s_1\le H_1\) على \(t\)، ونقاطعه مع المجال الذي يفرضه الشرط \(L_2\le s_2\le H_2\). إذا كان التقاطع غير فارغ، فالمرشح صالح.
تنتهي التطبيقات إلى أن أكبر مضاعف صالح هو
$$m=\frac{123}{59}.$$
وبالنسبة إلى هذه القيمة تكون اختزالات المجموعات الثلاث هي
$$\frac{123\cdot 5}{59\cdot 41}=\frac{15}{59},\qquad \frac{123\cdot 59}{59\cdot 41}=3=\frac{3}{1},\qquad \frac{123\cdot 59}{59\cdot 90}=\frac{41}{30}.$$
إذًا تصبح معاملات المجموعات
$$ (d_0,n_0)=(59,15),\qquad (d_1,n_1)=(1,3),\qquad (d_2,n_2)=(30,41). $$
والحدود العليا المقابلة هي
$$H_0=\min\!\left(\left\lfloor\frac{5248}{59}\right\rfloor,\left\lfloor\frac{640}{15}\right\rfloor\right)=42,$$
$$H_1=\min\!\left(\left\lfloor\frac{1312}{1}\right\rfloor,\left\lfloor\frac{1888}{3}\right\rfloor\right)+\min\!\left(\left\lfloor\frac{2624}{1}\right\rfloor,\left\lfloor\frac{3776}{3}\right\rfloor\right)+\min\!\left(\left\lfloor\frac{3936}{1}\right\rfloor,\left\lfloor\frac{5664}{3}\right\rfloor\right)=629+1258+1888=3775,$$
$$H_2=\min\!\left(\left\lfloor\frac{5760}{30}\right\rfloor,\left\lfloor\frac{3776}{41}\right\rfloor\right)=92.$$
أما المعاملات فتصبح
$$ (c_0,c_1,c_2)=(19971264,-6037824,-67344960)=464448\,(43,-13,-145). $$
وهكذا يغدو شرط الإمكان مكافئًا للمعادلة
$$43s_0-13s_1-145s_2=0.$$
ومن الاختيارات الصالحة
$$ (s_0,s_1,s_2)=(7,12,1), $$
لأن \(43\cdot 7-13\cdot 12-145\cdot 1=0\). كما أن القيمة \(s_1=12\) في المجموعة الوسطى يمكن تحقيقها بسهولة، مثلًا بالتوزيع \(1,1,10\) بين أصناف هذه المجموعة الثلاثة. يبيّن هذا المثال عمليًا لماذا ينجح المرشح \(\frac{123}{59}\).
تنفذ تطبيقات C++ وPython وJava هذا الاشتقاق حرفيًا. فهي لا تعدّد خماسيات عشوائية من القيم، بل تنشئ مجموعة المرشحين النسبيين التي يفرضها الصنف الأول ثم تختبر كل مرشح باستخدام حساب صحيح دقيق.
تمر الخوارزمية على جميع الاختيارات الصحيحة الموجبة الممكنة للصنف الأول، وتكوّن الكسر المختزل \(\frac{41b}{5a}\)، ثم تستبعد الحالات ذات \(m\le 1\)، وترتّب الكسور الباقية وتحذف التكرار منها. بهذه الخطوة يتشكل فضاء البحث الكامل والمنتهي.
بالنسبة إلى مرشح ثابت \(m=\frac{u}{v}\)، تحسب الخوارزمية نسب المجموعات الثلاث في صورتها المختزلة \(\frac{n_g}{d_g}\)، ثم تحسب الحد الأعلى لكل صنف ومجال كل مجموع \(s_g\). وإذا لم يبقَ لأي صنف قيمة موجبة مقبولة، يُرفض المرشح مباشرة.
أما إذا بقي ممكنًا، فتُبنى المعاملات \(c_g=vT_Qd_g-uT_Pn_g\)، ثم تُجرَّب جميع قيم \(s_0\) المسموح بها، ولكل قيمة منها يُفحص هل تملك المعادلة الثنائية المتبقية حلًا داخل المجالات. ويتم هذا الفحص باستخدام خوارزمية إقليدس الموسعة مع تضييق مجال المعامل الحر \(t\).
يمكن اختبار كل مرشح بصورة مستقلة عن الآخرين. ولذلك توزّع تطبيقا C++ وJava هذه الفحوص على عدة خيوط، بينما تنفذ نسخة Python الحساب نفسه على نحو تسلسلي. وبعد جمع جميع المرشحين الصالحين، يُعاد أكبر كسر مختزل.
يبدأ توليد المرشحين من \(5248\cdot 640=3{,}358{,}720\) كسرًا خامًا يفرضها الصنف الأول. ويكلف ترتيب هذه الكسور وإزالة التكرار منها زمنًا مقداره \(O(M\log M)\) حيث \(M=3{,}358{,}720\).
أما لكل مرشح مميز، فالمعالجة الخاصة بالمجموعات ثابتة الزمن، والحلقة الرئيسية تمر فقط على القيم الممكنة لـ \(s_0\). وبما أن المجموعة الأولى تحتوي صنفًا واحدًا فقط، فإن هذا المدى لا يتجاوز بضع مئات من القيم. كما أن فحص المعادلة الديوفانتية ذات المتغيرين يصبح \(O(1)\) بعد حساب القاسم المشترك الأكبر ومجالات المعامل الحر. لذلك يهيمن على الزمن العملي توليد المرشحين ثم مرحلة تحقق من الرتبة \(O(C\cdot R)\)، حيث \(C\) عدد المرشحين المتميزين و\(R\) عرض مجال المجموعة الأولى. أما الذاكرة فهي \(O(C)\) لتخزين قائمة المرشحين، مع مساحة مساعدة ثابتة لكل فحص. ويُحسِّن التنفيذ المتوازي زمن التشغيل الفعلي، لكنه لا يغير الرتبة التقاربية.