POLSKI SPOJ

Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

Zadanie w systemie SPOJ (trudne)

1609. Faktoryzacja

Kod zadania: FACTORIZ

Na wejściu dane jest k liczb. Dla każdej liczby wypisz jej rozbicie na iloczyn
czynników pierwszych.
Input:
W pierwszej linii, liczba k, k<=1000000.
W liniach 2 - k+1 liczby n_1,..,n_k, 1<=n_i<=8000000.
Output:
W linii i, czynniki pierwsze liczby b_i, w kolejno¶ci niemalej±cej,
rozdzielone znakami mnożenia.
Przykładowy input:
6
1
2
42
314
7999999
8000000
Przykładowy output:
1
2
2*3*7
2*157
7*199*5743
2*2*2*2*2*2*2*2*2*5*5*5*5*5*5

Dodane przez:Rafał Nowak
Data dodania:2007-06-04
Limit czasu wykonania programu:8s
Limit długości kodu źródłowego50000B
Języki programowania:All except: ERL JS PERL 6
Pochodzenie:Przemys³aw Uznañski

ukryj komentarze
2011-08-22 20:29:53 Piotr Turek
Skoro tak mówisz. ;)
Choć patrząc na moje zużycie pamięci, mam wrażenie, że w moim przypadku potrzebna byłaby raczej zmiana algorytmu niż optymalizacja ;D.
2011-08-22 13:19:06 Piotr Kąkol
@Piotr Turek - Aby uzyskać mój czas potrzebna jest właśnie optymalizacja, o której mówi Krzysztof i niezrozumiana przez Ciebie część wypowiedzi Sebastiana.
2011-08-20 17:45:00 Piotr Turek
Nie do końca wiem co masz na myśli mówiąc o 'poruszaniu się pomiędzy kolejnymi dzielnikami', ale faktycznie dość ciężko wymyślić tu coś ciekawego.
Sam jestem ciekawy jak niektórzy osiągnęli takie czasy. Moim zdaniem to bardzo mocna optymalizacja I/O + sprytne zapisywanie/zbieranie wyników.
2011-08-20 14:44:45 Sebastian Nowak
Ciężko wymyślić tutaj coś szybszego niż poruszanie się w O(1) pomiędzy kolejnymi dzielnikami. Można co najwyżej przyspieszyć ich tablicowanie używając bardziej rozbudowanych algorytmów, ale czy to ma sens?
2011-05-31 17:22:19 Piotr Kąkol
Rusz, rusz. ;-)
Kwestia algorytmu. :-)
2011-05-28 10:50:01 Krzysztof Lewko
Harda optymalizacja I/O daje AC. Bez tego ani rusz
SPOJ System © 2012 Sphere Research Labs | Projekty informatyczne i aplikacje na zamówienie. All Rights Reserved.