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


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 500
typedef 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 long

using 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;
}