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
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3757 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | awoo | 165 |
| 3 | adamant | 164 |
| 4 | TheScrasse | 159 |
| 5 | nor | 155 |
| 5 | maroonrk | 155 |
| 7 | -is-this-fft- | 152 |
| 8 | Petr | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
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 !!