Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

s_hertelli's blog

By s_hertelli, history, 3 months ago, In English,

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

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

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    43212157 I have tried this idea but i got a TLE . I am wondering if it can be improved

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it +2 Vote: I do not like it

      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);
      }
      
      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You could also use the __gcd(a,b) function in the bits/stdc++.h library

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how can we find the largest subset for which gcd>1 ?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      But how can we prove ,new gcd is greater than old gcd

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am not able to get this, can you explain a bit more or attach any link from where i can understand this.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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)