题解 P1865 【A % B Problem】

Space_Gold_Trash · 2019-07-07 15:47:20 · 题解

这是我在知道线性筛之前做的

做完打开题解，线性筛是什么鬼？？？？好高级的样子（后来发现这太弱了）

然后准备发个题解，然后一直拖到现在......

废话不多说，进入正题：

弱鸡用的弱鸡方法：

设f[i]表示1-i的质数个数

那么容易想到l-r的质数个数即为f[r]-f[l-1]

那么只要预处理f即可

很显然，当k是质数，则f[k]=f[k-1]+1

否则f[k]=f[k-1]

显然f[1]=0,f[0]=0

那么就可以初始化f了

#include <bits/stdc++.h>
using namespace std;
int a,b[1000001],n,m;
inline int zhi(int x){
    int i;
    if(x==1)return 0;
    else for(i=2;i<=sqrt(x);i++)if(x%i==0)return 0;
    return 1;
}
inline void shu( ){
    int i;
    b[1]=b[0]=0;
    for(i=2;i<=1000000;i++)
    if(zhi(i)==0)b[i]=b[i-1];
    else b[i]=b[i-1]+1;
}
int main( ){
    int num=0,i,j,k,x,y;
    shu( );
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++){
        num=0;
        scanf("%d %d",&x,&y);
        if(x<1||y>m){printf("Crossing the line\n");continue;}
        else printf("%d\n",b[y]-b[x-1]);
    }
}

能过，数据太水

题解 P1865 【A % B Problem】

求赞