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