6118. Funkcja σ [SIGMA_PL]

[ALBI_sof]

Zadanie: pl.spoj.com/problems/SIGMA_PL/
--
Jak przyspieszyć mój algorytm?

-- kod usunięty --

[kokosek_sof1]

Możesz to zrobić do sqrt(n) zamiast do n, ale musisz coś dodać w zamian za to.
Pomyśl. Masz np. n=24. No i oto dzielniki:
1,2,3,4,6,8,12,24 <- w takiej kolejności Ty je dodajesz i przeszukujesz do n. Pomyśl, co byś musiał/a dodać, żeby przeszukiwać do sqrt(n).

[Spykaj]

Jakieś podchwytliwe testy?

dla 1000000000 odp to 2497558338 ?

[kokosek_sof1]

Tak, ale dla 999999999 wypisze 1534205464.

[Spykaj]

Bardzo dziękuję

[Hauleth]

Pewnie kod wygląda tak:

for(int i = 1; i*i < num; ++i)
    if(num % i) sum += i;

Przez co jest ten kod błędny. Pomyśl dlaczego.

[xan_sof]

Popatrz na moją pierwszą odpowiedź do tematu. Skoro znajdujesz jeden dzielnik to i jesteś w stanie znaleźć drugi, dzięki czemu potrzebne jest tak mało kroków No chyba że to będzie ta sama liczba, ale na to wpadniesz i poprawisz później

[gong911]

Zrobiłem tak: najpierw szukam najmniejszego dzielnika szukanej liczby(szukam aż do pierwiastka z tej liczby - w przypadku liczby pierwszej wyświetlam szukana liczba+1).
Jak już mi znajdzie ten dzielnik(np dla 49 będzie 7 --> szukam zaczynając od 2) to zawężam działanie while'a nie do <=a/2 tylko <=a/dzielnik...
Wyniki podaje dobre i wydaje mi się ze sprawniej mu to wychodzi... Jednak nadal przekraczam limit czasu (1s) ;/

Chyba jednak zostawię to zadanie może kiedy indziej je zrobię

Dziękuję ci @adam_bak i @Hauleth za wskazówki

[xan_sof]

Nie wiem czy jest sens z tym czekać, blisko jesteś No zobacz.. Niech naszą badaną liczbą będzie 36. Natrafiając na jej pierwszy dzielnik = 2 od razu jesteśmy w stanie policzyć też kolejny (tylko od końca) 36/2=18. No bo po co my to robimy do sqrt(36)? A no właśnie po to żeby nie liczyć właściwie tego samego dwa razy. Chwila i masz AC

[matbas]

https://ideone.com/VTBd8K Ktos pomoze? Ciagle WA mimo tego ze nie moge znalezc bledu.

[redysz]

Opanuj wyświetlanie. Dla:

1
3491888400

Masz:

0

[manjaro]

Da radę zmieścić się w czysie w Pyhonie czy nie ma sensu się męczyć?

[pawoj20]

Nie sprawdzalem wszystkie odmiany pythona.
Jedną osobę znalazłem pl.spoj.com/ranks/SIGMA_PL/lang=PYTH%202.7
Edycja: na koncu adresu jest fragment o jezyku programowania. Jakie sa mozliwe fragmenty mozna sprawdzic na liscie problemow klikajac link za nazwa jezyka. Sam tego nie wymyslilem…

[manjaro]

Bardzo Ci dziekuję, nie wiem jak to znalazłeś mi się wyświetlają najlepsze wyniki maksymalnie do strony 11, a dalej już nie.