洛谷P1865 A%B Problem

题面：

 

 这道题很明显是一道数论的题目，涉及的内容主要为素数的问题。首先看数据范围，其实这道题的数据范围是很水的。因此在这里主要介绍2种方法。

法一，首先题目给出了给定区间右端点的最大值，因此我们对于每一个输入的l和r，要先进行判断其是否合法，只有合法的区间才能进一步处理。而合法的标准是右端点r<=m且左端点l>=1（注意这里要小心，不要想当然，题目中出了四个点来卡它）。

因此我们可以对于每一个给定的合法区间l到r，枚举l到r中的所有元素，依次判断该元素是否为素数。如果为素数，则cnt++。这里对于素数的判断我使用了O(√n)的试除法。很明显该方法时间复杂度过大。

代码（含注释）：

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,i,l,r,h,cnt;
inline bool prime(int n){//判断每一个数是否为素数
    if(n<2){//<2的数一定不是素数，要小心
        return false;
    }else{
        int j;
        for(j=2;j*j<=n;j++){//进行枚举
            if(n%j==0){//如果n有2~√n的质因子，则n一定非质
                return false;
            }
        }
    }
    return true;
}
int main(){
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d %d",&l,&r);
        if(r>m||l<1){//判断区间是否合法
            printf("Crossing the line
");
        }else{
            cnt=0;//统计每个区间内的素数个数
            for(h=l;h<=r;h++){
                if(prime(h)==true){
                    cnt++;
                }
            }
            printf("%d
",cnt);
        }
    }
    return 0;
}

分数：81分（完全没有想到！）

法二，既然法一出现了超时，那我们就要想方法进行优化。在法一中，TLE的主要原因便是对于同一个素数需要进行多次判断。而如果能够在一定的预处理基础上将O(√n)变成O(1)，那么时间就加快了。

题目明显预先给出了r的最大值，目的即是启发我们进行预处理。因此我们可以在O(n)的时间复杂度内预先找出1~m中的质数（我使用了线性筛），然后进行寻找和统计。

代码（含注释）：

#include<iostream>
#include<cstdio>
using namespace std;
int n,m,i,j,l,r,h,cnt,num;
int prime[100000005],v[100000005];
int main(){
    scanf("%d %d",&n,&m);
    num=0;//质数数量
    for(i=2;i<=m;i++){
        if(v[i]==0){//i是质数 
            v[i]=i;//质数的最小质因子是他自己
            prime[++num]=i;//记录质数 
        }
        for(j=1;j<=num;j++){//给当前的数i乘上一个质因子 
            if(prime[j]>v[i]||prime[j]>m/i){
                break;//i有比prime[j]更小的质因子，或者超出n的范围 
            }
            v[i*prime[j]]=prime[j];
        }
    }
    for(i=1;i<=n;i++){
        scanf("%d %d",&l,&r);
        if(r>m||l<1){
            printf("Crossing the line
");
        }else{
            cnt=0;
            for(h=1;h<=m;h++){
                if(prime[h]>=l&&prime[h]<=r){
                    cnt++;
                }
            }
            printf("%d
",cnt);
        }
    }
    return 0;
}

即可获得AC。