# 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 20002int 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("%d\n", ind);    }    return 0;}//`