Zadanie: pl.spoj.com/problems/TROJKI/
--
Cóż... Trochę się łudziłem, że wymyśliłem coś co działa szybko, a przynajmniej na tyle szybko, żeby się załapać w limicie czasu. Wyniki mam dobre na pewno, tylko (a raczej aż, bo wolałbym WA) TLE. Myślę, że wklejanie kodu nie ma większego sensu, więc opiszę moją wizję rozwiązania. Gdy program pobiera liczbę 'x' zaczynam poszukiwanie trójek pitagorejskich, z których każda liczba jest <= x, jednak ograniczam się do poszukiwania trójek tylko takich podstawowych, gdzie (powiedzmy, że trójka to liczby -> a,b,c) 'a' oraz 'b' mają NWD = 1. A więc są to trójki nie będące wielokrotnością innych trójek. Gdy już znajduję taka 'oryginalną' trójkę, zapisuję do tablicy (sortując przez wstawianie, chyba najbardziej logiczne tutaj, bo wymyślanie i wypisywanie trójek odbywa się jednocześnie, w celu zaoszczędzenia operacji) trójki będące wielokrotnością tej znalezionej trójki, oczywiście z warunkiem, aby każda z liczb była <= x. Jeszcze w tej samej pętli wypisuję oryginalną trójkę, i jeśli są jakieś pierwsze w kolejności leksykograficznej przed nią 'trójki wielokrotności' w tablicy, to je wypisuję przedtem. Oczywiście wszystko super, mimo iż nie wyszło bo jestem bogatszy w nowe doświadczenie.. Mianowicie nie ważne jak bardzo oszczędzam na operacjach i usprawniam to mój algorytm ma bardzo dużą złożoność obliczeniową, zgadza się? Jak jest limit 1s to wiadomo że w tego typu zadaniu nie ważne jak bym oszczędzał 3 pętle i tak nie przejdą, są dyskwalifikowane? Nawet jak często nie wykonują się całe? Wszystko przez to, że ogólny zamysł jest zbyt naiwny?
Czy wobec tego można by prosić o jakąś drobną wskazówkę? Dokąd, w którą stronę pójść w rozpracowywaniu tego zadanka? Ograniczyć pewnie liczbę pętli, ale do tego być może brakuje mi jakiejś wiedzy matematycznej.. Bardzo byłbym wdzięczny za jakiekolwiek naprowadzenie (zarwałem poprzednią nockę przez to zadanie 
).
