3

开始时,seq数组已清零。请注意seq数组的第一个元素的下标是0 而非 1。

void something (int jump) {
  for (int i = 0; i < N; i += jump)
    ++seq[i];
}

调用了 something 函数\(K\) 次，第 \(i\) 次调用时 \(jump=X_i\)。

接下来有 \(Q\) 次查询，每次查询包含两个整数 \(L_i,R_i\) ，对于每组查询请输出\(∑^{R_i}_{k=L_i}seq[k]\) 。

输入格式
第一行：\(N,\)K。 接下来一行 \(K\)个整数，第i 个为\(X_i\) 。 第$ N+2$ 行：\(Q\)。 接下来 \(Q\) 行：每行两个整数\(L_i,R_i\) 。

输出格式
共 \(Q\)行，第\(i\) 行包含第\(i\) 组查询的答案。

样例1
input

10 4
1 1 2 1
3
0 9
2 6
7 7

output

35
18
3

样例2
input

11 3
3 7 10
3
0 10
2 6
7 7

output

8
2
1

数据范围
\(1≤N,K,Q≤10^6,1≤X_i≤N,0≤L_i
时间限制：2S

空间限制：256MB

求\(l\)到r的和我们只用把所有\(seq[i]\)求出来后求个前缀 就行了，所以主要问题是怎样快速求出seq.
观察到\(x_i\)全部小于n，所以如果可以保证\(1\)~\(n\)每个数字都只是遍历一次，就可以达到调和级数枚举。我们可以数一下每一种数出现了多少次，然后一并加上就可以了。遍历1到n，然后把相同的数一起加。

#include
const int N=1e6+5;
int n,k,q,c[N],x,y;
long long seq[N],s[N];
int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;i++)
		scanf("%d",&x),++c[x];
	for(int i=1;i<=n;i++)
		if(c[i])
			for(int j=0;j*i