Codeforces и Polygon могут быть недоступны в период с 23 мая, 7:00 (МСК) по 23 мая, 11:00 (МСК) в связи с проведением технических работ. ×

Int64 gcd computation is too slow in Haskell

Правка en2, от codefforces, 2020-12-25 09:59:28

Problem: https://codeforces.com/contest/1459/problem/C

The algorithm is all about up to 4*10^5 many gcd computations of large integers. It appears that Haskell is too slow do just this!

C++ code passes in ~ 1.3 sec.

Haskell code on the other hand exceeds TL (2 sec). Switching from Integer to Int64 did not help a bit.

Disappointing. Your thoughts? Any ways to optimize?

Теги haskell, int64, gcd, performance

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en10 Английский codefforces 2020-12-26 11:29:23 165 Tiny change: '\n**Update**\nIt tur' -> '\n**Update:**\nIt tur'
en9 Английский codefforces 2020-12-25 10:19:44 0 (published)
en8 Английский codefforces 2020-12-25 10:19:23 26 Tiny change: 'oblem/C)\nThe [alg' -> 'oblem/C)\n\nThe [alg'
en7 Английский codefforces 2020-12-25 10:15:34 51 Tiny change: 'erforming 4⋅1054⋅1054⋅10^5 gcd compu' -> 'erforming $$4⋅10^5$$ gcd compu'
en6 Английский codefforces 2020-12-25 10:09:59 10 Tiny change: 'erforming ``4⋅10^5`` gcd compu' -> 'erforming $$$4⋅10^5$$$ gcd compu'
en5 Английский codefforces 2020-12-25 10:08:36 12 Tiny change: 'erforming 400000 gcd compu' -> 'erforming ``4⋅10^5`` gcd compu'
en4 Английский codefforces 2020-12-25 10:07:30 54
en3 Английский codefforces 2020-12-25 10:02:40 50
en2 Английский codefforces 2020-12-25 09:59:28 410
en1 Английский codefforces 2020-12-25 09:51:05 846 Initial revision (saved to drafts)