C++ :

#include <cstdlib>
#include <algorithm>
#include <cstdio>
#include <cmath>
#define maxn 100005
using namespace std;
struct q{
    int l, r, k, t, ans;
    q(int l, int r, int k, int t) : l(l), r(r), k(k), t(t){}
    q(){}
}sline[maxn];
int n, m;
int pos[maxn];
int size;
void init(){
    for (int i = 0; i < n; i++){
        pos[i] = i / size;
    }
}
bool cmp(q a, q b){
    if (pos[a.l] != pos[b.l]) return pos[a.l] < pos[b.l];
    return a.r < b.r;
}
bool cmp2(q a, q b){
    return a.t < b.t;
}
bool vis[maxn];
int line[maxn];
int l, r;
int save[maxn];
int ct;
int num[maxn];
int cnt[maxn];
int gcd(int l, int r){
    return (r == 0) ? l : gcd(r, l % r);
}
void ins(int x){
    if (num[cnt[line[x]]]) num[cnt[line[x]]]--;
    cnt[line[x]]++;
    save[ct++] = cnt[line[x]];
    num[cnt[line[x]]]++;
}
void del(int x){
    if (num[cnt[line[x]]]) num[cnt[line[x]]]--;
    if(cnt[line[x]]) cnt[line[x]]--;
    save[ct++] = cnt[line[x]];
    num[cnt[line[x]]]++;
}
int get_ans(int k){
    int ans = 0;
    int temp = 0;
    for (int i = 0; i < ct; i++){
        if (!vis[save[i]] && num[save[i]]){
            vis[save[i]] = 1;
            if (save[i] != 0 && gcd(k, save[i]) == 1) ans += num[save[i]];
            save[temp++] = save[i];
        }
    }
    ct = temp;
    for (int i = 0; i < ct; i++) vis[save[i]] = 0;
    return ans;
}
int main(){
    scanf("%d%d", &n, &m);
    size = (int)sqrt(n) + 1;
    init();
    int l, r, k;
    for (int i = 0; i < n; i++){
        scanf("%d", &line[i]);
    }
    for (int i = 0; i < m; i++){
        scanf("%d%d%d", &l, &r, &k);
        sline[i] = q(l - 1, r - 1, k, i);
    }
    sort(sline, sline + m, cmp);
    l = 0, r = -1;
    
    for (int i = 0; i < m; i++){
        while (r > sline[i].r) del(r--);
        while (r < sline[i].r) ins(++r);
        while (l > sline[i].l) ins(--l);
        while (l < sline[i].l) del(l++);
        sline[i].ans = get_ans(sline[i].k);
    }
    sort(sline, sline + m, cmp2);
    for (int i = 0; i < m; i++){
        printf("%d\n", sline[i].ans);
    }
    return 0;
}