Wrong Solution getting AC on CF#446 Div1/A

Revision en1, by lixolas, 2017-11-18 19:29:05

Hello everyone,

on last CodeForces, the problem A of Div1 Contest (this problem) was about some GCD operations. My solution (by the way, very unexpected, despite the fact that some people may have used the same idea) used binary search and some prefix sum matrix (for checking if GCD on range equals 1), only considering primes smaller than 40,050. Although it is getting AC (my solution during the contest, translated to english), I figured out a case where it fails:

2

524287 524287

(actually, it could be any prime numbers greater than 40,050.)

In this case the solution is -1 (because the gcd of two equal numbers is the number itself), however, my code prints 1 as the answer. Is there anything that can be done about this?

Tags weak testcases, gcd, round 446, div1 a

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English lixolas 2017-11-18 20:10:00 25 Tiny change: ' the way, very unexpected, despite ' -> ' the way, totally overkill, despite ' (published)
en1 English lixolas 2017-11-18 19:29:05 889 Initial revision (saved to drafts)