题解 P1865 【A % B Problem】

Ameiyo · 2018-01-12 12:26:07 · 题解

本蒟蒻的第一篇题解。。。。

先跑一边循环，求出1-i中的质数个数（包括i）存在pri数组中。

最后再跑一遍循环，解决问题。

首先是判断素数：

    bool prime(int a){
        if(a<2)return false;
        for(int i=2;i<=sqrt(a);++i)
            if(a%i==0)return false;
        return true;
    }

然后是从1-m存储：

for(i=1;i<=m;++i)

        if(prime(i))pri[i]+=pri[i-1]+1;//如果是质数就是前一个加一 

        else pri[i]=pri[i-1];//如果不是素数就等于前一个 

最后是解决问题：

    for(i=1;i<=n;++i){
            int l,r;
            cin>>l>>r;
            if(l<1 || r>m){//越界 
                cout<<"Crossing the line\n";
                continue;//重新判断循环条件 
            }
            int d=pri[r]-pri[l];//l-r之间的个数等于1-r的个数减去1-l的个数 （包括r不包括l） 
            if(pri[l]!=pri[l-1])d++;//如果pri[l]=pri[l-1]就说明l不是质数，反之l是质数，所以要加上l这一个 
            cout<<d<<endl;
        }

全代码（AC）：

    #include <bits/stdc++.h>
    using namespace std;
    const int x=1000005;
    int n,m,pri[x];
    bool prime(int a){
        if(a<2)return false;
        for(int i=2;i<=sqrt(a);++i)
            if(a%i==0)return false;
        return true;
    }
    int main(){
        ios::sync_with_stdio(false);
        cin>>n>>m;
        int i;
        for(i=1;i<=m;++i)
            if(prime(i))pri[i]+=pri[i-1]+1;
            else pri[i]=pri[i-1];
        for(i=1;i<=n;++i){
            int l,r;
            cin>>l>>r;
            if(l<1 || r>m){
                cout<<"Crossing the line\n";
                continue;
            }
            int d=pri[r]-pri[l];
            if(pri[l]!=pri[l-1])d++;
            cout<<d<<endl;
        }
        return 0;
    }