HackerEarth Query multiples problem solution YASH PAL, 31 July 2024 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("%dn", ind); } return 0;}// coding problems