xennygrimmato's blog

Number of pairs with GCD(a[i], a[j]) > 1
By xennygrimmato, 10 years ago, In English

Q. Given an array of N positive integers, find all pairs (ai, aj) such that Gcd(ai, aj) > 1.

1 ≤ N ≤ 105

How can this problem be solved?

GCD Recruit — HackerEarth

Tags gcd
  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (32)
| Write comment?
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is this problem from?

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

Just look closer at the constraints :) It also can be solved for A[i] <  = 106 .

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you give another hint? I first thought precomputing euler totient function for all A[i] ≤ 3000 might be useful, but I dont think that will help.

    → Reply
»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I solved a similar problem on codechef a while ago, the key idea is to use inclusion-exclusion principle. If a number X is a multiple of Y, then X is also a multiple of all of Y's divisors. Now count for each number Y, the number of it's multiples that are present in your array and then apply inclusion-exclusion by making a loop from the highest Y to 1 and excluding every number's divisors.

The problem can be solved using mobius inversion formula but I don't understand it quite well but you can find pretty good tutorials about it on the internet!

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you link me to the codechef problem ?

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I contemplated over the idea but I am thinking that I need to know how many multiples of particular i <=10^6 are present in array how will that be processed efficiently! !please explain the process clearly !!

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      The problem constraints say that the largest number in the input will be less than 10^6 so here is what you can do. Put all number in a hash map with the frequency of each number.

      Now say that you want to find how many multiples of 2 there are, you will go through the hash map and sum the counts of 2, 4, 6, 8, 10, 12, ...... 10^6

      This will take time roughly equal to 10^6/2.

      Now if you want to do the same thing for other numbers X from 3 to n, everyone will take (10^6/X) so the total time complexity would be 10^6/2 + 10^6/3 + 10^6/4 + 10^6/5 + ...... 10^6/n

      This is equal to 10^6*(1/2 + 1/3 + 1/4 + 1/5 ..... + 1/n). The summation from 1/1 to 1/n is called harmonic series and is bounded by O (ln (n))

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

        nlog(n) not always works if n is 1e6. It gives TLE (sometimes on cf and many times of CSES).

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

        ig, we do not have to find only multiples for eg: let say x is 6: then possible pairs could be from — (3,6,9,12...)

        so basically we need to find smallest factor that divides a[i] and then we check for count like freq[a[i]]+freq[a[i]+primeFactor]+freq[a[i]+primeFactor*2]+...

        which wont be feasible.

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

        i am missing something here .will we not end up over counting ?

        for eg-if we have a[i]=6 (2*3) and a[j]=12 (2*3*3)

        we will count them as pair first for 2 and then 3 as well

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

          I think you are looking at it wrong.

          We don't need to loop x from 2 to n. We need loop over the numbers present in the map. For the case, u gave a = {6, 12}, we will loop over this array and see that for x = 6, how many multiples of it exist.

          for a = {2,3,6,12} we will loop as follows,

          1. x = 2, -> (multiples present are 6, 12) -> (2, 6), (2,12)

          2. x = 3, -> (multiples present are 6, 12) -> (3, 6), (3,12)

          3. x = 6, -> (multiples present are 12) -> (6,12)

          so, ans = 5

          → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I bit of more explanations would be highly appreciated!

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 5   Vote: I like it 0 Vote: I do not like it

      As there are atmost 8 distinct primes that a number can have a[i]<=10^6 , when we are at an index i we find how many of the numbers from 1 to i-1 have atleast one common divisor with the a[i] this can be done by PIE(PRINCIPLE OF INCLUSION AND EXCLUSION) ,we keep a global array G[] which tells us the number of elements which are divisible by the the index ,i.e G[i] = denotes number of elements uptill now which have i as one of it's divisors,to find no of elements from 1 to i-1 we use PIE and as our current number has atmost 8 distinct divisors say p1,p2,p3,...p8 then with PIE we can find total number of elements which are divisible by atleast one of the p1,p2,p3,...p8 ..we need G[p1 U p2 U p3 ...p8]= sigma G[pi] — sigma G[pi ^ pj] + sigma G[pi ^ pj ^pk] ......so on {^ =denotes intersection} time complexity of this step is 2^8 and after this step we will update G[] and increament at all positions where the a[i] is divisible similarly by generating 2^8 possible distinct prime combinations so overall time complexity = O(N*2^8).

      upd: try this one this is based on modified PIE https://www.hackerearth.com/problem/algorithm/altered-primes/description/

      → Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

my algorithm for this problem went through about 2.7*10^7 operations. The basic idea was to have 2 for loops, one going from 1 to 3000 [say with variable i] and the other from 1 to 3000 [with variable j]. Then, if the gcd of the two is >0, and they are not the same, then you add X[i]*X[j] to one counter, where X[i] is the number of occurrences of integer i in the list provided. Else, if the gcd is > 0 and they are the same, then add X[i]*(X[i]-1)/2 to a separate counter. If we let the first counter be a and the second b, the answer is (a/2)+b

Note: This approach is much much easier then exclusion-inclusion principle.

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    ur idea is correct, but i think the answer should be instead of .

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      no it should be (a/2)+b, as we are not counting each pair b twice (for example, (2,2) is only counted once).

      → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        let a = [1, 2, 2, 3]. the correct answer for this case is 1 (only the pair (2, 2) is valid).
        but according to ur method, x = [1, 2, 1]. this gives answer as 2, which is wrong.

        → Reply
        • »
          »
          »
          »
          »
          10 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ohh I'm sorry... I mistyped when I put down my algorithm :P

          It is fixed [it should be x[i]*(x[i]-1)/2]

          → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    They used the inclusion-exclusion principle to solve it when A[i]<=10^6

    → Reply
»
6 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Hello everyone, I came across a similar problem -- for a vector a, display number of unordered pairs such that GCD(a[i],a[j])>b such that i!=j. a[] and b are given in the input. Please help.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -22 Vote: I do not like it

// ~~~~~ include <bits/stdc++.h>

using namespace std;

define MAXN 1000001

define int long long

int spf[MAXN];

int M[MAXN] = { 0 };

void sieve()

{ 

spf[1] = 1; 
for (int i = 2; i < MAXN; i++) 


    spf[i] = i; 


for (int i = 4; i < MAXN; i += 2) 
    spf[i] = 2; 


for (int i = 3; i * i < MAXN; i++) { 


    if (spf[i] == i) { 
       for (int j = i * i; j < MAXN; j += i) 


         if (spf[j] == j) 
          spf[j] = i; 
    } 
}

}

void counthash(int x) { int temp; while (x != 1) { temp = spf[x]; if (x % temp == 0) { M[spf[x]]++; x = x / spf[x]; return; } while (x % temp == 0) x = x / temp; } }

void generate(int arr[], int n) { sieve(); for (int i = 0; i < n; i++) counthash(arr[i]);

}

set getF(int x) { set s; while (x != 1) { s.insert(spf[x]); x = x / spf[x]; } return s; }

int32_t main() { int n ; cin>>n;

int a[n],b[n]; 
for(int &i:a) cin>>i;
for(int &i:b) cin>>i;
// int x[] = {12,14,16};
generate(a, n);

int c=0;
for (int i=0;i<n;i++){
    set<int> s;
    s= getF(b[i]);
    int mx=0;
    // cout<<b[i]<<" ";
    for(int i :s ){
        mx+=M[i];
        // cout<<i<<" ";
        // cout<<M[i]<<endl;
        }
        // cout<<endl<<" \n";
    c+=mx;    
}
// cout<<M[3];
cout<<c;
return 0;

}

~~~~~

//Here is the implementation.

→ Reply
»
23 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how can we solve it for a[i] < 10^9 made a hash map for values present in array then used 2 loop as follows for(int i=2; i<1000000000; i++){ for(int j=i; j<1000000000; j+=i){ if(mp.find(j) != mp.end()){ cnt[i]++; } } } where cnt[i] counts multiple of i present in array by it's not working for 10^9.

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

    Instead, let's calculate the no. of pairs i, j s.t. gcd(ai, aj) = 1 using mobius inversion and sqrt stuffs. Then we will know how to answer the original question. $$$S = \sum_{i = 1\cap i\subset A}^{N}\sum_{j = 1\cap j\subset A}^{N}[gcd(i, j) = 1] \newline = \sum_{i = 1\cap i\subset A}^{N}\sum_{j = 1\cap j\subset A}^{N}\sum_{d|gcd(i, j)}^{}\mu(d) \newline = \sum_{d = 1}^{N}\mu(d)(\sum_{i = 1\cap d\cdot i\subset A}^{N / d}1)^{2} \newline = \sum_{d = 1}^{N}\mu(d)\cdot (no. of\, multiples\, of\, d \subset A)^{2}$$$ Now we obeserve that each element of A has at most 10 divisors in (1e7, 1e9]. So for d <= 1e7 we loop to get 1st part of S where d <= 1e7 after precalculating no. of multiples of d in A and precalculating mobius values of all no.s upto 1e7. $$$\newline$$$ And to get 2nd part of S where d in (1e7, 1e9]: we create an array which contains all factors in (1e7, 1e9] of each element (these are ai / (10 smallest factors of ai)), then we can loop through the multiples of each element of this array and count how many of them are present. Also calculate mobius of each d present in this array. O(nsqrt(n) + 10*n*10^2). Actually, there can be at most 5 or 6 factors of ai in (1e7, 1e9] so I believe it would be possible to squeeze this within TL.

    → Reply
»
5 months ago, # |
  Vote: I like it +18 Vote: I do not like it

sorry for necroposting but it's the same as this CSES task: https://www.cses.fi/problemset/task/2417

→ Reply