Count pairs from an array with even product of count of distinct prime factors

  

#include <bits/stdc++.h>

using namespace std;

#define MAX 1000000

  

void countOfPrimefactors(vector<int>& CountDistinct)

{

    bool prime[MAX + 1];

  

    for (int i = 0; i <= MAX; i++) {

        CountDistinct[i] = 0;

        prime[i] = true;

    }

  

    

    for (long long int i = 2; i <= MAX; i++) {

  

        if (prime[i] == true) {

            CountDistinct[i] = 1;

  

            for (long long int j = i * 2; j <= MAX;

                 j += i) {

  

                CountDistinct[j]++;

                prime[j] = false;

            }

        }

    }

}

  

int CountEvenPair(int A[], int B[], int N, int M)

{

    

    

    vector<int> countDistinct(MAX + 1);

  

    countOfPrimefactors(countDistinct);

  

    

    

    int evenCount = 0;

  

    

    

    int oddCount = 0;

  

    

    int evenPairs = 0;

  

    

    for (int i = 0; i < M; i++) {

  

        

        

  

        if (countDistinct[B[i]] == 0)

            continue;

  

        

        if (countDistinct[B[i]] & 1) {

  

            

            oddCount++;

        }

        else {

  

            

            evenCount++;

        }

    }

  

    for (int i = 0; i < N; i++) {

  

        

        

  

        if (countDistinct[A[i]] == 0)

            continue;

  

        

        if (countDistinct[A[i]] & 1) {

  

            

            evenPairs += (evenCount);

        }

  

        

        else {

  

            

            

            evenPairs += evenCount + oddCount;

        }

    }

  

    return evenPairs;

}

  

int main()

{

    int A[] = { 1, 2, 3 };

    int B[] = { 4, 5, 6 };

  

    int N = sizeof(A) / sizeof(A[0]);

    int M = sizeof(B) / sizeof(B[0]);

  

    cout << CountEvenPair(A, B, N, M);

  

    return 0;

}

Let's block ads! (Why?)