[SMWP_107] Francois i Wielomiany

0 Flares Twitter 0 Facebook 0 0 Flares ×

Link do zadania:
http://www.spoj.com/SMWP/problems/SMWP_107/

Opis problemu:
Naszym zadaniem jest wyznaczenie sumy odwrotności pierwiastków wielomianu przy założeniu, że wielomian n-tego stopnia ma n pierwiastków.

Rozwiązanie:
Podane wyżej założenie ma na celu wskazanie niejako metody rozwiązania problemu. Mianowicie skorzystamy tutaj ze wzorów Viete’a. Zauważmy, że:

dla W(x)=ax^2+bx+c, mamy
1/x1+1/x2=(x2+x1)/(x1x2)=(-b/a)*(a/c)=-b/c

dla W(x)=ax^3+bx^2+cx+d, mamy
1/x1+1/x2+1/x3=(x2x3+x1x3+x1x2)/(x1x2x3)=(c/a)*(-a/d)=-c/d

dla W(x)=ax^n+bx^(n-1)+…+px+q, mamy
1/x1+1/x2+…+1/xn=(x2…xn+x1…xn+…+x1x2…)/(x1x2…xn)=(±p/a)*(∓a/q)=-p/q

Dzięki tej obserwacji nasz problem sprowadza się tylko do wykonania jednego działania, mianowicie suma odwrotności pierwiastków określonego w zadaniu wielomianu to tak naprawdę iloraz dwóch ostatnich niezerowych współczynników wielomianu. Należy także pamiętać o tym, że wynik podajemy w postaci skróconej tj przed wypisaniem współczynników skracamy je o ich NWD.

Print Friendly

Dodaj komentarz

Wymagane pola są oznaczone *.