E 捡贝壳 （分块 | 思维）

方法一：分块

1.块的大小时根号n，预处理分块数组
2.求解时，对于两边的l，r所在的块不论是否是整块都单独求，先求l所在的，求完后判l，r是否在一个块内（对于是否在一个块内，数组下标从0开始，这样的话数组下标/根号n所得的数字即是第几个块），是则可直接return
3.整块的

#include <bits/stdc++.h>

using namespace std;

int n, m;
int ar[100050];
int sum[320][100050];
int l, r, x, d;

void fenkuai()
{
    d = sqrt(n);
    for(int i = 0; i < n; ++i)
    {
        for(int j = 1; j * j <= ar[i]; ++j)
        {
            if(ar[i] % j == 0)
            {
                sum[i / d][j]++;
                if(ar[i] / j != j)  sum[i / d][ar[i] / j]++;
            }
        }
    }
}

int solve(int l, int r, int x)
{
    //cout << d << endl;
    int ans = 0;
    for(int i = l; i <= r && i / d == l / d; ++i) if(ar[i] % x == 0)    ans++;
    if(l / d == r / d)  return ans;
    for(int i = r / d * d; i <= r ; ++i)   if(ar[i] % x == 0)  ans++;
    for(int i = l / d + 1; i <= r / d - 1; ++i) ans += sum[i][x];
    return ans;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i) scanf("%d", &ar[i]);
    fenkuai();
    for(int i = 1; i <= m; ++i)
    {
        scanf("%d%d%d", &l, &r, &x);
        --l, --r;
        int ans = solve(l, r, x);
        printf("%d\n", ans);
    }
    return 0;
}

方法二：思维（vector + 二分查找）

分析：
据数据范围1e5，需要找x的倍数，我们可以枚举所有x的倍数，即2x，3x，...,一直到1e5（1e5不是1e9，可以枚举），我们需要判是否存在这些数，以及这些数是否在要求的区间内，很明显可以用一个容器来存每个数出现的位置。而这个容器肯定就是vector惹
（时间复杂度，空间复杂度都比分块优）
AC代码：

#include <bits/stdc++.h>

using namespace std;

int n, m;
int l, r, x;
int a, ans;
vector<int> vt[1000050];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d", &a);
        vt[a].push_back(i);
    }
    while(m--)
    {
        scanf("%d%d%d", &l, &r, &x);
        ans = 0;
        for(int i = x; i <= 100000; i += x) ans += upper_bound(vt[i].begin(), vt[i].end(), r) - lower_bound(vt[i].begin(), vt[i].end(), l);
        printf("%d\n", ans);
    }
    return 0;
}