HackerEarth Query multiples problem solution

In this HackerEarth Query multiples problem solution An array arr has indices numbered from 1 to N. You are given Q queries with two integers, iX in each.

Write a program to find the number of multiples of X in the array arr that falls between the (i^{th} index and the end of the array.

HackerEarth Query multiples problem solution.

#include <bits/stdc++.h>
using namespace std;
vector <int> divi [20005]; 
const int MAXN = 100005; 
int arr [MAXN]; 
struct node
{
    node * l;
    node * r; 
    int s; 
    node (node * a, node * b){
        l = a;
        r = b;
        s = 1;  
    }   
    node (){
        l = NULL;
        r = NULL;
        s = 1; 
    }
};
node * root [20005];
int gs (node * x){
    return ((x==NULL)?(0):(x->s)); 
}
void upd (int start, int end, int i, node *&x){
    if (start>i||end<i) return;
    if(start==end){
        if (x==NULL) x = new node(); 
        else x->s++; 
        return; 
    }
    if (x==NULL) x = new node();  
    upd(start,(start+end)/2, i, x->l); 
    upd((start+end)/2+1, end,i,x->r); 
    x->s = gs(x->l) + gs(x->r);
}
int query (int start, int end, int i, int j, node * x){
    if(x==0)return 0;
    if (start>j||end<i)return 0;
    if(start>=i&&end<=j)return gs(x); 
    return query(start,(start+end)/2,i,j,x->l)+query((start+end)/2+1,end,i,j,x->r); 
}
int main(){
    ios_base::sync_with_stdio(0); 
    for (int g=1; g<=20000; g++){
        for (int y=g; y<=20000; y+=g) divi[y].push_back(g); 
    }
    int N,Q; cin >> N>>Q; for (int g=1; g<=N; g++) cin >> arr[g]; 
    for (int g=1; g<=N-1; g++){
        for (int y : divi[arr[g]]) {
        upd (1, N, g, root[y]);}
    }
    for (int g=0;g<Q; g++){
        int i,X;cin>>i>>X;
        cout << query (1, N, i, N, root[X]) << 'n'; 
    }
    return 0; 
}

Second solution

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cctype>
#include<cstdlib>
#include<algorithm>
#include<bitset>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<ctime>
#include<complex>
#include<functional>
#include<climits>
#include<cassert>
#include<iterator>
#include<unordered_map>
#include<unordered_set>
using namespace std;

#define MAX 100002
#define MAX_VAL 20002
int n;
int q;
int a[MAX];
vector<int> di[MAX];
vector<int> V[MAX];
int main(){
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    for (int i = 1; i < MAX_VAL; i++){
        for (int j = i; j < MAX_VAL; j += i){
            di[j].push_back(i);
        }
    }
    for (int i = 0; i < n; i++){
        for (int j = 0; j < di[a[i]].size(); j++){
            V[di[a[i]][j]].push_back(i);
        }
    }
    while (q--){
        int i, x;
        scanf("%d%d", &i, &x);
        i--;
        int ind = lower_bound(V[x].begin(), V[x].end(),i) - V[x].begin();
        ind = V[x].size() - ind;
        printf("%dn", ind);
    }
    return 0;
}//

coding problems solutions