Int64 gcd computation is too slow in Haskell

Revision en3, by codefforces, 2020-12-25 10:02:40

Problem: https://codeforces.net/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 for even 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.

Any ideas on optimizing it?

Tags haskell, int64, gcd, performance

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en10 English codefforces 2020-12-26 11:29:23 165 Tiny change: '\n**Update**\nIt tur' -> '\n**Update:**\nIt tur'
en9 English codefforces 2020-12-25 10:19:44 0 (published)
en8 English codefforces 2020-12-25 10:19:23 26 Tiny change: 'oblem/C)\nThe [alg' -> 'oblem/C)\n\nThe [alg'
en7 English 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 English codefforces 2020-12-25 10:09:59 10 Tiny change: 'erforming ``4⋅10^5`` gcd compu' -> 'erforming $$$4⋅10^5$$$ gcd compu'
en5 English codefforces 2020-12-25 10:08:36 12 Tiny change: 'erforming 400000 gcd compu' -> 'erforming ``4⋅10^5`` gcd compu'
en4 English codefforces 2020-12-25 10:07:30 54
en3 English codefforces 2020-12-25 10:02:40 50
en2 English codefforces 2020-12-25 09:59:28 410
en1 English codefforces 2020-12-25 09:51:05 846 Initial revision (saved to drafts)