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

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 (x==NULL) x = new node();
else x->s++;
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(){
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

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){
for (int i = 0; i < n; i++){
for (int j = 0; j < di[a[i]].size(); j++){
while (q--){
int i, x;
scanf("%d%d", &i, &x);
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;