LBLADU - Editorial

editorial
,
1

PROBLEM LINK:

Practice

EXPLANATION:

Let us store all the prime numbers less than 1000 in a vector Primes, we will use this to check whether a_i is divisible by which prime numbers. Now, we create a map cnt[i] where cnt[i] denotes the count of the numbers that have the prime number i as a factor. Then, we can just iterate over all a_i and check for all values in Primes, if it is divisible then we increment the count of the prime by 1.

Now, the answer is simply the no. of pairs such that at least one of them has a factor P_i.

This is cnt[P_i]*(n-cnt[P_i]) + (cnt[P_i]*(cnt[P_i]-1))/2; that is we either chose both elements from cnt[p_i] or one from cnt[P_i] and one from the rest of the array (n-cnt[P_i]).

SOLUTION:

Setter's Solution 
    #include <bits/stdc++.h>
    using namespace std;
    typedef long long int ll;

    bool isprime(ll a) {
        for (int i = 2; i * i < a; ++i)
        {
            /* code */
            if (a % i == 0)return false;
        }
        return true;
    }

    int main() {
        std::vector<ll> Primes;
        for (int i = 2; i <= 1000; ++i)
        {
            /* code */
            if (isprime(i)) {
                Primes.push_back(i);
            }
        }
        ll T;
        cin >> T;
        while (T--) {
            ll n , m;
            cin >> n >> m;

            ll a, P;
            map<ll, ll> cnt;
            for (int i = 0; i < n; ++i)
            {
                /* code */
                cin >> a;

                for (auto i : Primes) {
                    if (a % i == 0) {
                        cnt[i]++;
                    }
                }
            }

            for (int i = 0; i < m; ++i)
            {
                /* code */
                cin >> P;
                cout << ((cnt[P] * (cnt[P] - 1)) / 2) + (cnt[P])*(n - cnt[P]) << " " ;
            }
            cout << endl;


        }
        return 0;
    }