game_changer007's blog

iita coding contest
By game_changer007, 9 years ago, In English

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

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

use segmented sieve approach to count it !!

→ Reply