Real problems.
Your next challenge.

Problem summary

An array contains distinct positive integers. Each query L R d asks how many positions in the inclusive range have a value dividing d or divisible by d. A value equal to d must be counted only once.

Constraints

1 ≤ N,Q ≤100000; 1 ≤ a[i],d ≤200000; all array values are distinct; 1 ≤ L ≤ R ≤ N.

Worked example

Original statement sample.

8 5
12 10 3 18 6 72 28 42
1 8 6
3 7 7
2 6 9
1 5 5
4 8 4

6 1 3 1 2

Solution analysis

1. Store position[value], or 0 if that value is absent. For every potential query value d, build a list of array positions satisfying one of the two divisibility relations. The distinct-value guarantee makes one position per number sufficient.
2. Enumerate every pair divisor,multiple by a sieve loop: multiple=divisor,2·divisor,... . If the multiple occurs in the array, add its position to the divisor’s query list. If the divisor occurs, add its position to the multiple’s query list. On the equal pair perform only the first addition, preventing double counting.
3. Sort every position list. A query answer is upper_bound(R)−lower_bound(L) in d’s list. In the sample query[1,8],d=6, the qualifying values are 12,3,18,6,72,42, yielding 6. For[4,8],d=4, only 72 and 28 qualify, yielding 2.

Why it works

The sieve enumerates exactly all ordered integer divisibility relationships. For a fixed d, every present multiple is added through the first rule and every present proper divisor through the second. These cases are disjoint except equality, which is deliberately included once. Sorting does not change membership; the two binary searches count exactly the retained positions in the inclusive interval.

Watch out. The array values are distinct; without that promise, position[value] would lose occurrences. Count equality only once. Both divisors and multiples matter: checking only a[i]%d==0 misses proper divisors of d.

An independently written complete program with standard headers.

#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    int queries;
    cin>>n>>queries;
    const int limit=200000;
    vector<int>position(limit+1,0);
    for(int index=1;index<=n;index++){
        int value;
        cin>>value;
        position[value]=index;
    }
    vector<vector<int>>matching(limit+1);
    for(int divisor=1;divisor<=limit;divisor++){
        for(int multiple=divisor;multiple<=limit;multiple+=divisor){
            if(position[multiple]!=0){
                matching[divisor].push_back(position[multiple]);
            }
            // Equality already belongs to the first case.
            if(multiple!=divisor&&position[divisor]!=0){
                matching[multiple].push_back(position[divisor]);
            }
        }
    }
    for(auto&positions:matching){
        sort(positions.begin(),positions.end());
    }
    for(int query=0;query<queries;query++){
        int left;
        int right;
        int value;
        cin>>left>>right>>value;
        const auto&positions=matching[value];
        int answer=static_cast<int>(upper_bound(positions.begin(),positions.end(),right)-
            lower_bound(positions.begin(),positions.end(),left));
        if(query>0){
            cout<<' ';
        }
        cout<<answer;
    }
    cout<<'\n';
}