题解 P1865 【A % B Problem】
引领天下
2018-06-23 18:37:09
这题大家应该都能看出来要用筛法+前缀和吧……~~所以我觉得这题顶多普及-~~
所以我来讲两个优化：
# 1. 其实前缀和并不用再开一个数组
# 2. 前缀和其实并不是非要套在循环里绕，完了再特判，只需要再开一个循环就可以了
具体看代码：
```cpp
#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("");
}
}//至于某些多打的部分是快读+快输，个人喜好。
```