捡贝壳

链接：https://ac.nowcoder.com/acm/contest/13504/E

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
小明来到一片海滩上，他很喜欢捡贝壳，但他只喜欢质量为x的倍数的贝壳。
贝壳被排列成一条直线，下标从1到n编号,小明打算从编号为区间[l,r]\left [l,r \right ][l,r]的贝壳中,捡起所有他喜欢的贝壳。你能帮他计算出他能捡多少贝壳吗。
给出一个大小为n(n≤105)n(n\le10^5)n(n≤105)的数组，下标从1到n编号，a1,a2,…ana_1,a_2,…a_na1​,a2​,…an​(ai≤105)(a_i \le 10^5)(ai​≤105))表示贝壳的质量。
给出q(q≤5∗104)q(q\le5*10^4)q(q≤5∗104)次询问，每次询问包含3个整数l,r,x(1≤l≤r≤n,1≤x≤105)l,r,x(1\le l \le r\le n,1\le x\le 10^5)l,r,x(1≤l≤r≤n,1≤x≤105)，对于每次询问，输出一行整数,表示这次询问中能捡到的贝壳数。
输入描述:
第一行给出两个整数n和q，含义如上所示。
第二行给出n个整数表示a1,a2,…ana_1,a_2,…a_na1​,a2​,…an​
接下来q行，每行3个整数l,r,x，含义如上所示
输出描述:
对于每次询问输出该次询问中能捡到的贝壳数
示例1
输入
5 3
1 2 3 4 5
1 3 2
1 5 3
2 5 4
输出
1
1
1
示例2
输入
10 3
5532 24380 19363 11022 23965 22383 27049 22357 30453 7451
1 6 2
3 10 10
1 10 9
输出
3
0
1

思路：使用数组存放数字num所在的下标，每次询问查询数字x及其倍数所在的下标是否在所需区间 [ l, r ] 内即可。

#include<iostream>
#include<vector>
using namespace std;
vector<int> arr[100005];
int n, q;
int main() {cin >> n >> q;for (int i = 1; i <= n; i++) {int num;cin >> num;arr[num].push_back(i);//num所在的下标i压入数组}for (int i = 1; i <= q; i++) {int l, r, x, ans = 0;cin >> l >> r >> x;for (int j = x; j <= 100000; j += x) {//x的倍数for (int k = 0; k < arr[j].size(); k++) {if (arr[j][k] >= l&&arr[j][k] <= r) ans++;//数字j所在的下标是否在区间内。}}cout << ans << '\n';}return 0;
}