Misir Kəsrləri

Misir Orta Krallığı dövründə misirlilər kəsrləri yazmaq üçün bir yol inkişaf etdirdilər. Tam ədədin hiyeroglifinə bir simvol əlavə etmək həmin ədədin qarşılığını təmsil edirdi. Bu, $1/n$ (vahid kəsr) formasında hər hansı bir kəsri yazmağı asanlaşdırdı — sadəcə $n$ üçün hiyeroglifə qarşılıq simvolunu əlavə edin.

$m/n$ formasında, burada m > 1 olan bir kəsri təmsil etmək üçün birbaşa yol yox idi. Bunun əvəzinə, belə bir kəsr vahid kəsrlərin cəmi kimi yazılırdı. Məsələn, $3/4$ kəsri belə yazıla bilərdi:

Qeyd edək ki, bir neçə cəm eyni nəticəni verə bilər; məsələn, həmçinin belə yazıla bilər:

Sizin işiniz kəsrini "acgöz" axtarış ilə vahid kəsrlərin cəmi kimi yazmaqdır. Bu yolla, siz hər dəfə orijinal kəsrdən qalan hissədən mümkün olan ən böyük vahid kəsri çıxırsınız, və bu prosesi sıfıra çatana qədər təkrarlayırsınız. Məsələn, kəsrini nəzərdən keçirin. Acgöz axtarış üç addımda cəmini tapır:

Qeyd edin ki, hər addımda orijinal kəsrdən qalan hissədən mümkün olan ən böyük vahid kəsr çıxılır.

Həllin çox böyük olmaması üçün əlavə məhdudiyyət: Hər dəfə bir vahid kəsr çıxardıqda, qalan kəsrin məxrəci mütləq $1000000$-dən kiçik olmalıdır. Məsələn, kəsrini nəzərdən keçirin. İlk iki vahid kəsr və olar, və nəticədə qalar. Bu mərhələdə çıxara biləcəyimiz ən böyük vahid kəsr olar, və

nəticədə məxrəci $1000000$-dən böyük olan bir kəsr alınar və bu vahid kəsr istifadə oluna bilməz. Növbəti ən mümkün vahid kəsrə keçirik: , nəticədə

qalar. İndi məxrəci $1000000$-dən kiçikdir və bu vahid kəsri istifadə etmək mümkündür, beləliklə son cavab olar.

Bu halda yalnız bir kəsri keçmək lazım gəldi. Ümumiyyətlə, işləyə biləcəkini tapmaq üçün bir çox kəsri keçmək lazım gələ bilər. Araşdırma apararkən böyük məxrəcli kəsrlərlə işləmək lazım gələr; proqramınızın vaxtında bitməsi üçün səmərəli olun.

Böyük ədədləri saxlamaq üçün kifayət qədər böyük tip seçin. Məxrəclər $1000000$-ə qədər məhdudlaşdırılsa da, aralıq məxrəclər 10^{12}-ə çata bilər. Buna görə 64-bitlik tam ədəd (Java-da long, C/C++-da long long) tələb olunur.

Acgöz alqoritm təbiəti üzrə həmişə məxrəci $1000000$-dən kiçik olan bir cavab tapacaq—istənilən kəsr ən azı öz məxrəci ilə belə yaza bilər. Məsələn:

Giriş

Giriş bir neçə kəsrdən ibarətdir, hər sətrdə bir kəsr. Hər sətrdə $M$ və $N$ tam ədədləri (1 < M < N < 100), kəsrini təmsil edir. $M$ və $N$-in ortaq böləni yoxdur (vuruşdan böyük). Girişin sonu $00$ ilə göstərilir.

Çıxış

Hər kəsr üçün bir sətirdə D[1] \le D[2] \le D[3] \le \dots ədədləri çap edin ki,

Bu, acgöz axtarışının $1000000$ məxrəci şərtinə ilk uyğun cəmi olmalıdır. Hər ədəd arada bir boşluqla verilməlidir, əvvəlində və ya sonunda boşluq olmamalıdır.