I was unable to solve a problem in onsite coding round of iiit allahabad.
Given N numbers.Then Q queries of the form L R D, How many number from index L to R are divisible by D
1<=L<=R<=100000
1<=D<100000
N<=100000
Q<=100000
input:
N-number of integers then N integers, Q qeuries of form L R D eg-
10
4 6 3 5 18 9 2 4 7 22
2
1 3 2
2 5 3
output
2
3
If the numbers are small (I guess they are), they don't have many divisors. Maybe you can create a list L[d] for each divisor d, which holds indices of numbers divisible by d. Then each query consists of just two binary searches on L[d]: first one counts number of indices not exceeding r, second one finds the number of indices smaller than l.
use segmented sieve approach to count it !!