przekręcanie się long longów
Ostatnio zmodyfikowano 2019-05-23 12:46
Mamcia 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/2213i taki kod: https://wandbox.org/permlink/XozBh83LBn7Hp3oGNa 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? |
|
killjoy |
» 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. |
|
« 1 » |