题解 P1865 【A % B Problem】

发表于 更新于 阅读次数： Waline：
P1865 【A % B Problem】题解。

这题大家应该都能看出来要用筛法+前缀和吧……所以我觉得这题顶多普及-

所以我来讲两个优化：

1. 其实前缀和并不用再开一个数组

2. 前缀和其实并不是非要套在循环里绕，完了再特判，只需要再开一个循环就可以了

具体看代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
int n,m,l,r,a[1000000];
void prime(){
    for (int i=2;i<=m;i++)if (!a[i])
    for (int j=i*2;j<=m;j+=i)a[j]=1;//标准线筛
    for (int i=2;i<=m;i++)a[i]=!a[i],a[i]+=a[i-1];//处理前缀和：直接在同一个数组里处理，a[i]=!a[i]是把原来对质数的标记0改成1，对合数的标记1改成0，然后就可以放心地加上前面的了
}
template <typename _Tp>
inline void read(_Tp &x){
    int w=1;char c=0;x=0;
    while (c^'-'&&(c<'0'||c>'9'))c=getchar();
    if (c=='-')w=-1,c=getchar();
    while (c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x*=w;
}
inline void write(int n){
    if(n==0) return;
    write(n/10);
    putchar(n%10+'0');
}
int main(){
    read(n),read(m);
    prime();
    while (n--){
        read(l),read(r);
        if (l<1||l>m||r<1||r>m){puts("Crossing the line");continue;}
        if (a[r]-a[l-1])write(a[r]-a[l-1]);//标准前缀和输出方式
        else putchar('0');puts("");
    }
}//至于某些多打的部分是快读+快输，个人喜好。