EVEIS - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Nihal Mittal

DIFFICULTY:

EASY

PREREQUISITES:

Sieve of Eratosthenes, Hashing

PROBLEM:

The problem requires you to first find all divisors of the elements of the given array and then count the number of pairs such that count(a[i]) + count(a[j]) = k, 1<=i,j<=N,i!=j where the count function denotes the number of divisors of any number x and a denotes the given array.

QUICK EXPLANATION:

The most efficient way to calculate the number of divisors is by using the Sieve of Eratosthenes. Once all the divisors are found out we can calculate the numbers of pairs using hashing.

EXPLANATION:

The primary problem is to first efficiently calculate all the divisors of elements of the array. For the first subtask we can use brute force to calculate the number of divisors. For the second subtask however we must use the logarithmic Sieve of Eratosthenes for the solution to pass. Since the greatest number in an array can be 10^6 we can precalculate all the numbers from 1 to 10^6 using sieve.
After we get the count array we maintain a hash map that keeps track of the count of all elements with the same number of divisors. After that we iterate on the array elements and whenever we encounter an element a[i] we check whether k - a[i] exists in the hash map and update the answer accordingly.

TIME COMPLEXITY

Time complexity is O(N * log(logN)) per test case where N = 10^6 for the precalculation using Sieve Of Eratosthenes.

SOLUTIONS:

Setter's Solution 
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define mk make_pair
#define pb push_back
#define in insert
#define se second
#define fi first
#define mod 1000000007
#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define all(v) (v).begin(),(v).end()
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(0);
#define pii pair<ll,ll>
#define vi(x) vector<x>
#define maxn 100005
using namespace std;
ll dive[1000006];
void sieve()
{
	ll i,j;
	for(i=1;i<=1000003;i++)
	{
		for(j=i;j<=1000003;j += i)
		{
			dive[j]++;
		}
	}
}

signed main()
{
    fast;
    #ifndef ONLINE_JUDGE
	freopen("input.txt","r", stdin);
    freopen("output.txt","w",stdout);
    #endif
    ll n,i,j,k,ans=0;
    sieve();
    cin>>n>>k;
    ll b[n+2];
    ll x;
    map<ll,ll> ma;
    for(i=0;i<n;i++)
    {
    	cin>>x;
    	b[i] = dive[x];
    }
    for(i=0;i<n;i++) ma[b[i]]++;
    for(i=0;i<n;i++)
    {
        if(k-b[i]>=0 and b[i]!= (k-b[i]))
        {
            ans += ma[b[i]]*ma[k-b[i]];
            ma[b[i]] = 0;
            ma[k-b[i]] = 0;
        }
        else if(b[i]==(k-b[i]))
        {
            ans += (ma[b[i]] * (ma[b[i]] - 1))/2;
            ma[b[i]] = 0;
        }
    }
    cout<<ans;
}
1 Like