Szalony układ równań

[rekurencja]

Otóż drodzy matematycy potrzebuję pomocy w rozwiązaniu tego o to pięknego układu równań:

\(\displaystyle{ \begin{cases} n=p*q*r \\ \varphi (n)=(p-1)*(q-1)*(r-1) \\ \sigma (n)=(p+1)*(q+1)*(r+1) \end{cases}}\)

gdzie p, q, i r to liczby pierwsze, a n, \(\displaystyle{ \varphi (n)}\) i \(\displaystyle{ \sigma (n)}\) są podane na wejściu. Czy ktoś ma pomysł jak z tego wyliczyć p, q i r ?? Ja nie jestem na tyle biegły w matematyce (1 kl liceum), a rozwiązanie tego układu potrzebuje do pewnego zadania informatycznego. Z góry dziękuję za pomoc ...

[BettyBoo]

Zaplątałeś się trochę, to nie jest żaden układ równań. Jeśli n jest podane, to \(\displaystyle{ \varphi(n),\ \sigma(n)}\) są po prostu tyle równe, jeśli p,q i r sa liczbami pierwszymi.

Trzeba więc znaleźć rozkład liczby n na czynniki pierwsze i tyle. Wystarczy sprawdzać po kolei, która liczba pierwsza dzieli n. Możesz też zastosować algorytm Fermata (opis np ), jeśli wiesz (lub przewidujesz), że dzielniki tej liczby są duże i są stosunkowo "blisko" siebie.

Pozdrawiam.

[rekurencja]

A gdybym ci to zapisał tak ....

\(\displaystyle{ \begin{cases} 30=p*q*r \\ 8=(p-1)*(q-1)*(r-1) \\ 72=(p+1)*(q+1)*(r+1) \end{cases}}\)

To powiedział byś, ze to jest układ równan ?? Sęk w tym, że to jest zadanie algorytmiczne i w danym tescie liczba przykladow moze byc nawet 20000 a n<=10^15 co przy limitach 0.4 - 1 sec na test powoduje ze rozkladanie za kazdym razem tych liczb na czynniki pierwsze a potem dopasowywanie do tych rownan nie może sie powieść

[Rogal]

Po pierwsze, powiedziałabyś. Po drugie czytaj, co do Ciebie piszą a nie wymądrzaj się.
Sprawdziłeś choć ten algorytm Fermata?

[rekurencja]

Po drugie czytaj, co do Ciebie piszą a nie wymądrzaj się.
Sprawdziłeś choć ten algorytm Fermata?

Sorry, ale na to, ze mogę rozłożyć tą liczbę na czynniki pierwsze to wpadłem kilka godzin temu. Sęk w tym, że to ma działać szybko a nie tylko działać. Nie rozumiem, gdzie zaobserwowałeś moje wymądrzanie się. Nie jestem, żadnym dzieckiem, które strzela jakimiś limitami czasowymi i ograniczeniami po to, żeby sie 'pochwalić'. Ja po prostu rozwiązuje zadanie z pewnej ligi programistycznej i aby je rozwiązać optymalnie poprosiłem grzecznie, was matematyków o pomoc w rozwiązaniu tego układu. Gdyby nie dało się go rozwiązać to raczej Wolfram by tego nie policzył prawda ?? .

[Rogal]

Nadal nie rozumiesz - to nie jest układ równań. Ostatnie dwa równania wynikają z pierwszego tak, jak je zapisałeś. Wolframowi podałeś co innego, podałeś mu konkretny układ.
Jeżeli robisz coś na Ligę, to chyba w założeniach tej Ligi nie stoi, że wskazana jest pomoc z zewnątrz? Ponadto, gdyby matematycznie ten problem był łatwo rozwiązywalny, to nikt by takiego zadania nie dał.
Masz się wykazać właśnie zdolnościami programistycznymi, czyli napisać dobry algorytm.
Czytaj co się do Ciebie pisze.
Tego Fermata to chyba dalej nie sprawdziłeś, co?

[rekurencja]

Dziękuję za zainteresowanie tematem, jednak chciałbym coś wyjaśnić. Wolframowi podałem konkretny przykład po przecież rózne sa dane wejsciowe a mnie chodzi o zasadę. Ja wiem, że te 2 rownania wynikaja z pierwszego, gdyby nie wynikały to by się wyniki nie zgadzaly. W tym zadaniu mamy na wejsciu podany: n , tocjent z n, sumę dzielnikow n i mamy policzyc p, q i r. Co do regulaminu ligi, to nie proszę nikogo o pomoc w napisaniu rozwiązania tego zadania. Proszę tylko o pomoc w matematycznym wyliczeniu wyliczeniu p q i r na podstawie tych rownan. Jest to pomoc czysto teoretyczna, gdyż będę jeszcze musiał znaleźć sposób na algorytm liczący to. Gdybym umiał przekształcic ten układ w postać dzieki ktorej moglbym to obliczyc jakims znanym mi algorytmem np. metoda wyznacznikowa to bym tutaj nie pisał jednak nie umiem i dlatego proszę o pomoc w samym przekształceniu tego. Podałem konkretny przykład powyżej z konkretnymi liczbami, a skoro Wolfram to policzyl to znaczy ze można to policzyc (bo nie wierzę w to, że Wolfram w locie stosuje rozwiązanie brutalne, czyli rozkład na czynniki i dopasowywanie, zreszta skąd miałby wiedziec ze tak to trzeba zrobic). Co do algorytmu Fermata, to nie ma on tutaj zastosowania dlatego, że dla przypadków krańcowych działałby wolniej niż brutal ...

[Rogal]

Cóż, ogólnie taki układ to raczej będzie prowadził (na moje oko) do równania trzeciego stopnia, a rozwiązania tego w ogólności nie są fajne.
To trzeba jakoś subtelniej, bo to w końcu teoria liczb.