watchdogs132's blog

By watchdogs132, history, 6 years ago, In English

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 .

  • Vote: I like it
  • -7
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it -6 Vote: I do not like it
4
22 33 55 1

Your program outputs 3

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If you know Bangla, then you can understand it from here. You can also use google translator.