HackerEarth Similar Chocolates problem solution

In this HackerEarth Similar Chocolates problem solution, There are N chocolates denoted by array A where A[i] is the length of the i-th chocolate. Alice can melt each chocolate and then convert it into chocolate whose length is any divisor of the number A[i]. So, chocolate of length A[i] can be converted into X different types of chocolate where X is the count of divisors of the number A[i]. So you need to count the total unordered pair of chocolates such that their X value is the same.

HackerEarth Similar chocolate problem solution.

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "\n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
int a[100001];
int divi[1000001];
LL f[1000001];
int main()
    {
        ios_base::sync_with_stdio(0);
        int n;
        for(int i = 1; i <= 1000000; i++){
            for(int j = i; j <= 1000000; j += i){
                divi[j]++;
            }
        }
        cin >> n;
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            f[divi[a[i]]]++;
        }
        LL ans = 0;  
        for(int i = 1; i <= 1000000; i++){
            ans = ans + (f[i] * (f[i] - 1)) / 2;
        }
        cout << ans << endl;
    }

Second solution

#include <bits/stdc++.h>

using namespace std;

map<int, int> hash_map1;
map<int, int> hash_map2;

int divisors(int n) {
    if(hash_map1.find(n) != hash_map1.end())
        return hash_map1[n];
    int cnt = 0;
    for(int i = 1; i <= sqrt(n); i ++) {
        if(n % i == 0) {
            cnt ++;
            if(n / i != i)
                cnt ++;
        }
    }
    hash_map1[n] = cnt;
    return hash_map1[n];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    int inp;
    for(int i = 0; i < n; i ++) {
        cin >> inp;
        hash_map2[divisors(inp)] ++;
    }
    long long ans = 0;
    for(auto i : hash_map2) {
        long long x = i.second;
        ans += (x * (x - 1)) / 2;
    }
    cout << ans;
    return 0;
}