przekręcanie się long longów
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

przekręcanie się long longów

AutorWiadomość
Temat założony przez niniejszego użytkownika
przekręcanie się long longów
» 2019-05-23 11:15:39
Mam takie zadanie

http://solve.edu.pl/contests​/download_desc/2213
i taki kod:
https://wandbox.org/permlink​/XozBh83LBn7Hp3oG

Na dwóch testach pokazuje mi błędą odpowiedź. Prawdopodobnie przekręcają się long longi przy mnożeniu w funkcji szybkiego potęgowania.
Pomyślałem o użyciu algorytmu mnożenia rosyjskich chłopów.
To jest prawie taka sama funkcja jak ta którą mam do szybkiego potęgowania, tylko mnożenie trzeba zamienić na dodawanie i...za cholerę mi to nie wychodzi :-(
Ktoś pomoże?
P-174688
» 2019-05-23 12:46:48
Algorytm jest błędny, ale nie ze względu na long longi (tym bardziej, że działasz na modulo). Według twojego programu 625000450000081 jest liczbą pierwszą. A tak na prawdę jest to liczba złożona, która mieści się w zakresie 10^17 (tym bardziej w long longu, o ile jest 64 bit). Dowód na złożoność: Czynniki liczby 625000450000081.
P-174689
« 1 »
 Strona 1 z 1