捡贝壳（分块算法）

#include<iostream>
#include<cmath> 
using namespace std;
const int maxn = 1e5+5;
int dat[maxn];//这个数组中存放着输入的数据 
int sum[350][maxn];//这个数组的第一维表示每一个块，每个块一般都是根号n的长度，因为数据范围是1e5所以开350就够了，第二维表示这一块中有多少个某个数字的倍数 
int n,q; 
void blocked()//分块+信息处理 
{
	int  sz=sqrt(n);//获得每个分块的长度 
	for(int i=0;i<n;++i)//从0开始分块比较方便表示 
	{
		for(int j=1;j*j<=dat[i];++j)//找j的倍数 
		{
			if(dat[i]%j==0)//找到j的倍数 
			{
				sum[i/sz][j]++;//让这一分块的j的倍数数量++
				if(dat[i]/j!=j) sum[i/sz][dat[i]/j]++;//让这一分块的dat[i]/j的倍数数量++，!=j是因为j的倍数数量前面加过了，再加会重复 
			}
		}
	}
}
int query(int l,int r,int x)
{
	int sz=sqrt(n);//获得每个分块的长度 
	int ans=0;
	for(int i=l;i<=r&&l/sz==i/sz;++i)//遍历最左边的元素到第一个整块的起点这一段中间的数据,l/sz==i/sz说明l和i在同一块中 
	{
		if(dat[i]%x==0) ans++;//若其中有元素是x的倍数，ans就++ 
	}
	if(l/sz==r/sz)//满足这个条件说明l到r这一段是在同一个整块中，若如此，则上面的计算结果就是最终的答案
	{
		return ans; 
	}
	for(int i=r;i>=l&&i/sz==r/sz;--i)//遍历最右边的元素到第一个整块的终点这一段中间的数据,r/sz==i/sz说明r和i在同一块中
	{
		if(dat[i]%x==0) ans++;//若其中有元素是x的倍数，ans就++
	}
	for(int i=l/sz+1;i<=r/sz-1;++i)//最后统计整块的数据 
	{
		ans+=sum[i][x];//ans加上第i块的x的倍数数量 
	} 
	return ans;
}
int main()
{
	cin>>n>>q;
	for(int i=0;i<n;++i)
	{
		cin>>dat[i];
	}
	blocked();//分块 
	int l,r,x;
	for(int i=1;i<=q;++i)
	{
		cin>>l>>r>>x;
		l--;//因为数据存储的时候编号是从0开始的 
		r--; 
		cout<<query(l,r,x)<<endl;
	}
	return 0;
}
/*
5 3
1 2 3 4 5
1 3 2
1 5 3
2 5 4

1
1
1
*/
/*
10 3
5532 24380 19363 11022 23965 22383 27049 22357 30453 7451
1 6 2
3 10 10
1 10 9

3
0
1
*/