E 捡贝壳

题意：

给你n个贝壳，每个贝壳有不同的质量，进行q次询问，询问的是区间[l, r]中的贝壳质量是x的倍数的有多少个

思路1：

一开始最暴力的方法是用个二维数组存因子的前缀和，然后就可以作差直接查询，但是空间不允许，就得放弃

所以，我们就可以采取分块的方法，将n个贝壳进行分块，每一块的大小不超过，然后像线段树求区间和一样一段段的求即可

• 分块操作：我这里选择的是输入的时候就直接分块，你也可以像其他人那样写个函数，等输入完了再分

  分块的时候最好是从0这个数开始，比如0 1 2 3 4 5 6 7 8，块是3，前三个数除以3刚好是0，但如果你从1开始计数，那就不方便了

for(int i = 1; i <= n; ++i){
        ar[i] = IntRead();//快读
        for(int j = 1; j * j <= ar[i]; ++j){//质因数分解
            if(ar[i] % j == 0){//判断能否整除j
                tr[(i - 1) / cnt + 1][j]++;//能整出就对该块的j进行++操作，这里从1输入，所以对i-1进行判块，且我这里cnt从1开始是为了后面的操作做准备，一会讲
                if(ar[i] / j != j)tr[(i - 1) / cnt + 1][ar[i] / j]++;//对于j这个因子，肯定有ar[i] / j这另一个因子，但需要判断这两个因子是不是相同的，也就是ar[i]找个数可能是平方数，那他开平方的数就只需要计算一遍
            }
        }
    }

• 求解：

分两种情况：

1. l 和 r 在一个块里面，这时候就直接打个暴力，从 l 循环到 r，最多最多也就跑300多，因为分的块最大也就是$$
2. l 和 r 不在一个块里面，这个时候就分三部分进行运算

见图：由l 到 a块的结束 + a块与b块中间的块 + b块的开始到 r

int getnum(int l, int r, int x){
  //判断l和r在哪个块里面，注意这里要让块的值是大于等于1的，所以就得加一
    int a = l / cnt + 1, b = r / cnt + 1;
    int sum = 0;
    if(a == b){//判断在同一个块内
        for(int i = l; i <= r; ++i){
            if(ar[i] % x == 0)sum++;//直接莽暴力
        }
        return sum;
    }
  //第一部分： 从l 开始，到 a块的结束的位置打暴力
    for(int i = l; i <= a * cnt; ++i){
        if(ar[i] % x == 0)sum++;
    }
  //第三部分 从 b块的开始到 r 打暴力
    for(int i = (b - 1) * cnt + 1; i <= r; ++i){
        if(ar[i] % x == 0)sum++;
    }
  //第三部分，计算中间到块的值
    for(int i = a + 1; i < b; ++i)sum += tr[i][x];
    return sum;
}

献上AC码：

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 100050 + 7
#define endl '\n'
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define mod 571373;
typedef  long long ll ;
//不开longlong见祖宗！
//
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, x, y, cnt, z;

int tr[320][MAX], ar[MAX];

int getnum(int l, int r, int x){
    int a = l / cnt + 1, b = r / cnt + 1;
    int sum = 0;
    if(a == b){
        for(int i = l; i <= r; ++i){
            if(ar[i] % x == 0)sum++;
        }
        return sum;
    }
    for(int i = l; i <= a * cnt; ++i){
        if(ar[i] % x == 0)sum++;
    }
    for(int i = (b - 1) * cnt + 1; i <= r; ++i){
        if(ar[i] % x == 0)sum++;
    }
    for(int i = a + 1; i < b; ++i)sum += tr[i][x];
    return sum;
}

int main(){
    n = IntRead();m = IntRead();
    cnt = sqrt(n);
    for(int i = 1; i <= n; ++i){
        ar[i] = IntRead();
        for(int j = 1; j * j <= ar[i]; ++j){
            if(ar[i] % j == 0){
                tr[(i - 1) / cnt + 1][j]++;
                if(ar[i] / j != j)tr[(i - 1) / cnt + 1][ar[i] / j]++;
            }
        }
    }
    while (m--) {
        x = IntRead(); y = IntRead();z = IntRead();
        cout<<getnum(x, y, z)<<endl;
    }
    return 0;
}

思路2: vector + 二分

对于这个题，数比较小，每个数都是小于1e5的，我们就可以采用枚举每个x的倍数，在给定区间去找

这里我们使用vector数组来存每个数的下标，便于二分查找，防T

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 100050 + 7
#define endl '\n'
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define mod 571373;
typedef  long long ll ;
//不开longlong见祖宗！
//
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, l, r, x, a, ans;
vector<int>tr[MAX];

int main(){
    n = IntRead();m = IntRead();
    for(int i = 1; i <= n; ++i){
        x = IntRead();
        tr[x].push_back(i);//把数为x的下标塞进去
    }
    while (m--) {
        l = IntRead(); r = IntRead();x = IntRead();
        ans = 0;
        for(int i = x; i <= MAX; i += x){//这里就相当于枚举每个x的倍数
            ans += upper_bound(tr[i].begin(), tr[i].end(), r) - lower_bound(tr[i].begin(), tr[i].end(), l);
//因为是找的给定区间的，我们就去二分，前一个二分是找大于r的第一个位置，后一个二分找的是大于等于 l 的第一个位置
        }
        cout<<ans<<endl;
    }
    return 0;
}