All Tracks Algorithms Searching Binary Search Problem

Query multiples
/

Binary search algorithm, Mathematics, Searching algorithm

Problem
Editorial
Analytics

An array \(arr\) has indices numbered from 1 to N. You are given Q queries with two integers, \(i X\) 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.

Input format

  • First line: Two space-separated integers \)N\( and \)Q\(
  • Second line: \)N\( space-separated integers (denoting the array \)arr\()
  • Next \)Q\( lines: Two space-separated integers, \)i\( and \)X\(

Output format

For each query, print the number of multiples of \)X\( in the array \)arr\( that falls between the \)i^{th} index and the end of the array.

Constraints

\(1 ≤ N ≤ 10^5\)
\(1 ≤ Q ≤ 10^5\)
\(1 ≤ X ≤ 20000\)
\(1 ≤ arr[i] ≤ 20000\)

SAMPLE INPUT
3 1
9 6 2
2 2
SAMPLE OUTPUT
2
Explanation

There are two numbers, 6 and 2, after the index 2 divisible by 2.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 64 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?