Enlarge GCD (Round #511) (WA)

Revision en2, by watchdogs132, 2018-11-29 19:55:40

Link to problem :https://codeforces.net/contest/1034/problem/A

Link to my submission: https://codeforces.net/contest/1034/submission/46372547

My approach: I divided the vector of the numbers by their gcd. Then I tried to find largest subsequence having gcd greater than 1. To do that , I used the Sieve of Eratosthenes to calculate least prime factor of every number upto 1.5*10^7 and stored it in array Primes. In the factorise function , I just increase the count of divisors and then return the answer(n-count of the divisor that occurred maximum number of times).

My code gives wrong answer for test case #9. The different between jury's answer and mine is small though . Also I have read the editorial and my approach is same as that of the editorial . I think the problem is with the sieve maybe , should it be in linear time? . Thank you .

Tags #primes, gcd, factor

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English watchdogs132 2018-11-29 19:55:40 2 Tiny change: 'he answer(count of t' -> 'he answer(n-count of t'
en1 English watchdogs132 2018-11-29 19:54:26 883 Initial revision (published)