前缀和练习1

【Suan 数区间统计】

蒜头君定义了一种数叫 suan 数：如果一个整数 x 是 suan 数，那么它必定能被给定的正整数 k 整除。现有 n 次询问，每次给出两个正整数 l, r（l <= r），请你统计区间 (l, r]（即不包含左端点 l）中有多少个整数是 suan 数。数据范围：1 <= n, k, l, r <= 10^5，且 l <= r。

下面是一段用于解决该问题的不完整 C++ 代码。它使用前缀和数组 s[i] 表示前 i 个整数中 suan 数的个数，从而实现区间查询。请在标有 ①~⑤ 的位置填入正确的表达式或语句。

#include

using namespace std;

int n, k, s[①]; // 询问次数，k的倍数

int main(){

    cin >> n >> k;

    for(int i=②; i<=100000; i++) { // 前i个数中k的倍数的个数

        if(③) s[i]=s[i-1]+1;     // 如果第i个数是k的倍数，总数+1

        else s[i]=④; // 否则不变

    }

    while(n--) {

        int l,r;

        cin >> l >> r;

        cout << ⑤ << endl;

    }

    return 0;

}

【咖啡温度】

蒜头君想泡咖啡喝。现在他得到了 n 份菜谱，每个菜谱上都给了两个数 l, r，代表温度区间在 [l, r] 度泡出来的咖啡会很好喝。

可是菜谱太多了，蒜头君一度感到疑惑。经过思考之后他得出了一个结论：某个温度只要有 k 份或者更多菜谱推荐，那么这个温度下泡出来的咖啡会很好喝。

现在他给出了 m 个温度区间，同样还是用 [l, r] 表示，现在求问每个区间里面有多少个整数，使得咖啡在这个温度下泡出来会很好喝？

输入格式：

第一行为三个整数 n, k, m。

第 2 ~ n+1 行，每行两个整数，代表菜谱里面的 l, r。

第 n+2 ~ n+m+1 行，每行两个整数，代表询问温度区间里面的 l, r。

输入的所有数都是正整数且不超过 2×10^5，且满足 l ≤ r，k ≤ n，且所有区间的长度之和不超过 10^7。

输出格式：

对于每个询问输出一行，为一个整数，表示有多少可用的温度。