Müəllimin Riyaziyyat Tərəfi#5835
Tələbələrin riyaziyyat dərslərində tez-tez yerinə yetirdikləri tapşırıqlardan biri polinom tənliklərini həll etməkdir. Məsələn, X^2 − 4X + 1 polinomu verildikdə, tələbələrdən onun köklərini (2 ±) tapmaq tələb olunur.
Əgər tələbələrin tapşırığı verilmiş polinomun köklərini tapmaqdırsa, müəllimin tapşırığı isə verilmiş kökü olan polinomu tapmaqdır. Xanım Galsone, sadə a + b kimi kvadrat tənliklərin həllindən bezmiş həvəsli bir riyaziyyat müəlliməsidir. O, daha mürəkkəb həlləri olan yüksək dərəcəli tənliklər qurmaq istəyir. Riyaziyyat dərslərində olduğu kimi, o, bütün əmsalların tam ədədlər olmasını və polinomun dərəcəsini mümkün qədər kiçik saxlamaq istəyir (verilmiş kökü olduğu halda). Zəhmət olmasa, müəllimə kömək etmək üçün bir proqram yazın.
Sizə aşağıdakı formada bir t ədədi verilir:
t = +
burada a və b fərqli sadə ədədlərdir, m və n isə 1-dən böyük tam ədədlərdir.
Bu məsələdə sizdən t-nin tam ədədlər üzərində minimal polinomunu tapmağınız tələb olunur. Bu polinom aşağıdakı şərtləri təmin etməlidir:
Əmsallar a_0, ..., a_d tam ədədlərdir və a_d > 0.
F(t) = 0.
Dərəcə d yuxarıdakı iki şərti təmin edən polinomlar arasında minimumdur.
F(X) primitivdir. Yəni, a_0, ..., a_d əmsallarının birdən böyük ümumi böləni yoxdur.
Məsələn, tam ədədlər üzərində + minimal polinomu F(X) = X^4−10X^2+1 olur. F(t) = 0 olduğunu yoxlamaq aşağıdakı kimi sadədir (α = , β = ).
F(t) = (α + β)^4 − 10(α + β)^2 + 1
= (α^4 + 4α^3β + 6α^2β^2 + 4αβ^3 + β^4) − 10(α^2 + 2αβ + β^2) + 1
= 9 + 12αβ + 36 + 8αβ + 4 − 10(3 + 2αβ + 2) + 1
= (9 + 36 + 4 − 50 + 1) + (12 + 8 − 20)αβ = 0
F(t) dərəcəsinin həqiqətən minimum olduğunu yoxlamaq bir az daha çətindir. Xoşbəxtlikdən, bu məsələdə verilmiş şərt altında, yəni a və b fərqli sadə ədədlərdir və m və n birdən böyükdür, minimal polinomun dərəcəsi həmişə mn-dir. Üstəlik, həmişə monikdir. Yəni, onun ən yüksək dərəcəli üzvünün əmsalı (a_d) birdir.
Giriş bir neçə datasetdən ibarətdir, hər biri aşağıdakı formatda.
a m b n
Bu sətir m + n ifadə edir. Son dataset dörd sıfırdan ibarət bir sətirlə tamamlanır. Bir sətirdəki ədədlər bir boşluqla ayrılır.
Hər bir dataset aşağıdakı şərtləri təmin edir:
m + n ≤ 4.
mn ≤ 20.
Cavabın a_0, ..., a_d əmsalları (−2^31 + 1) və (2^31 − 1) arasında, daxil olmaqla, yerləşir.
Hər bir dataset üçün onun tam ədədlər üzərində minimal polinomunun əmsallarını çıxış edin
F(X) = a_dX^d + a_{d−1}X^{d−1} + ··· + a_1X + a_0,
aşağıdakı formatda.
a_d a_{d−1} ... a_1 a_0
Mənfi olmayan tam ədədlər işarəsiz (+ və ya −) çap edilməlidir. Bir sətirdəki ədədlər bir boşluqla ayrılmalı və çıxışda başqa simvollar və ya əlavə boşluqlar olmamalıdır.
Nümunə 1