### s_hertelli's blog

By s_hertelli, history, 13 months ago, ,

1034A - Enlarge GCD There has been no editorial after the contest . so can someone help me to solve this problem ?

• -3

 » 13 months ago, # | ← Rev. 2 →   0 Suppose the gcd of the initial array is x. Divide every element by x. Now you simply find the largest subset which has gcd > 1.
•  » » 13 months ago, # ^ | ← Rev. 2 →   0 43212157 I have tried this idea but i got a TLE . I am wondering if it can be improved
•  » » » 13 months ago, # ^ | ← Rev. 2 →   +2 your gcd implementation is bugged.try this long long int gcd(long long int a, long long int b) { if (a==0) return b; return gcd(b % a, a); } 
•  » » » » 13 months ago, # ^ |   0 You could also use the __gcd(a,b) function in the bits/stdc++.h library
 » 13 months ago, # |   0 how can we find the largest subset for which gcd>1 ?
•  » » 13 months ago, # ^ |   0 For the remaining elements in our group, we have some prime p that divides them all, since otherwise their gcd would be one. Therefore, the prime is also  ≤ 1.5 * 107.You can just find all primes below that bound, and then count how many different numbers that prime appears in. To do this, just factor every a_i, and increment the primes's counters that appear in its factorization.
•  » » » 13 months ago, # ^ |   +1 But how can we prove ,new gcd is greater than old gcd
•  » » » » 13 months ago, # ^ |   +1 Because we divided all elements with old gcd, old gcd is 1. New gcd is >= p, with the prime we choose, so it is greater than the old gcd.
•  » » » 13 months ago, # ^ |   0 I am not able to get this, can you explain a bit more or attach any link from where i can understand this.
 » 13 months ago, # |   0 In their test no 4 , their input is: 2 1 7 with ans 1 which means 1 removal but according to this doesn't the answer become n-(no of occurrences of maximum element of the array)