# HackerEarth The Market problem solution

In this HackerEarth The Market problem solution There are N items in a market (indexed from 1 to N) each having a particular cost. The danger value of each item is given by the following pseudo code:

Danger(cost) {
danger_val = 0
for ( each i from 1 to cost) {
if( cost modulo i is 0  ) {
increase danger_val by 1
}
}
return danger_val
}
You are given Q queries that contain a range of items. You need to find the number of pairs of items that have the same danger value.

## HackerEarth The Market problem solution.

`#include <bits/stdc++.h>#define _ ios_base::sync_with_stdio(false);cin.tie(0);using namespace std;#define pb push_back#define pob pop_back#define pf push_front#define pof pop_front#define mp make_pair#define all(a) a.begin(),a.end()#define bitcnt(x) __builtin_popcountll(x)#define MOD 1000000007#define BASE 31#define BLOCK 500typedef unsigned long long int uint64;typedef long long int int64; int fact[1000006];int cur[250];int a[100005];int64 fin[100005];int64 ans=0;struct query{    int l,r,id;};bool cmp(query a,query b){    if((a.l/BLOCK)!=(b.l/BLOCK))    return (a.l/BLOCK)<(b.l/BLOCK);    return a.r<b.r;}vector<query>v;void add(int val){    ans+=cur[fact[val]];    cur[fact[val]]++;}void del(int val){    cur[fact[val]]--;    ans-=cur[fact[val]];}int main(){    fact[1]=1;    for(int i=2;i<=1000000;i++){        if(fact[i])        continue;        for(int j=i;j<=1000000;j+=i){            if(!fact[j])            fact[j]=1;                        int mul=1;            int val=j;            while((val%i)==0){                val/=i;                mul++;            }            fact[j]*=mul;        }    }    int n,l,r,q;    cin>>n;    for(int i=1;i<=n;i++)    scanf("%d",&a[i]);        cin>>q;    query tmp;    for(int i=1;i<=q;i++){        scanf("%d%d",&tmp.l,&tmp.r);        tmp.id=i;        v.pb(tmp);    }        sort(all(v),cmp);    l=1,r=0;        for(int i=0;i<v.size();i++){        tmp=v[i];        while(r<tmp.r){            r++;            add(a[r]);        }        while(l>tmp.l){            l--;            add(a[l]);        }                while(r>tmp.r){            del(a[r]);            r--;        }        while(l<tmp.l){            del(a[l]);            l++;        }        fin[v[i].id]=ans;    }        for(int i=1;i<=q;i++)    printf("%lld\n",fin[i]);    //fclose(stdout);    return 0;}`

### Second solution

`#include <bits/stdc++.h>#define lli long longusing namespace std;int cnt[1000005];int A[100005];int dp[100001][100];int tot;int idx[1005];void pre(){    for ( int i = 1; i <= 1000000; i++ ) {        for ( int j = i; j <= 1000000; j += i ) cnt[j]++;    }    return;}int main(){    pre();    int n,q,x,y;    lli ans;    tot = 1;    cin >> n;    assert(n >= 1 && n <= 100000);    for ( int i = 1; i <= n; i++ ) {        cin >> A[i];        assert(A[i] >= 1 && A[i] <= 1000000);        A[i] = cnt[A[i]];        if ( !idx[A[i]] ) idx[A[i]] = tot++;        A[i] = idx[A[i]];    }    assert(tot <= 100);    for ( int i = 1; i <= n; i++ ) {        for ( int j = 1; j < tot; j++ ) dp[i][j] = dp[i-1][j];        dp[i][A[i]]++;    }    cin >> q;    while ( q-- ) {        cin >> x >> y;        assert(x >= 1 && x <= n);        assert(y >= 1 && y <= n);        assert(x <= y);        ans = 0;        for ( int i = 1; i < tot; i++ ) {            lli val = dp[y][i] - dp[x-1][i];            val = (val*(val-1LL))/2;            ans += val;        }        cout << ans << endl;    }    return 0;}`