Where is this problem from?

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

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!

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.

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.

// ~~~~~ 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.

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.

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