E捡贝壳

小明来到一片海滩上，他很喜欢捡贝壳，但他只喜欢质量为x的倍数的贝壳。

贝壳被排列成一条直线，下标从1到n编号,小明打算从编号为区间 $\left [l,r \right ]$ 的贝壳中,捡起所有他喜欢的贝壳。你能帮他计算出他能捡多少贝壳吗。

给出一个大小为 $n(n\le10^5)$ 的数组，下标从1到n编号， $a_1,a_2,...a_n$ $(a_i \le 10^5)$ )表示贝壳的质量。

给出 $q(q\le5*10^4)$ 次询问，每次询问包含3个整数 $l,r,x(1\le l \le r\le n,1\le x\le 10^5)$ ，对于每次询问，输出一行整数,表示这次询问中能捡到的贝壳数。

#include<bits/stdc++.h> using namespace std; vector<int>v[100006]; int n,r,l,a,q,i; int main() { cin>>n>>q; for(i=1;i<=n;i++) { cin>>a; v[a].push_back(i); } int d; while(q--) { int ans=0; cin>>l>>r>>d; for(i=d;i<=1e5;i+=d) { for(auto j : v[i] ) ans+=j>=l&&j<=r; } cout<<ans<<endl; } }

详情