题解 P1865 【A % B Problem】

杨咩咩咩啊 · 2018-10-20 21:29:33 · 题解

首先，我认为我码风很丑。

好我们开始正经写题解。

【关键词】记忆化搜索，素数判断，AC

是的就是题目标签里的两个词，很水

【思路】

1，从1到m遍历，前缀和求出每个数及之前的质数个数。
2，1到n输入区间，直接查询：a[r]-a[l-1] ，输出。
（注意是L-1而不是L，因为包括L这里是故意用的大写L因为l和1太像不好区分）
3，提交，AC~
4，自己不太会判断时间复杂度，但是自己感觉我这个代码过不了可能会T，，，交了居然一遍AC也是蛮神奇的了hhh，可能是数据水叭

惯例附【代码】：

（建议思路看会的就自己写叭毕竟码风丑而且自己写记得才牢哇）

/*(^-^)*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
ll n,m,l,r,t,a[1000005];

bool judge(ll x)
{
    if(x==1)return false;//来个特判
    for(ll i=2;i<=sqrt(x);i++)
        if(x%i==0)return false;
    return true;
}
//简单的判断素数

int main()
{
    scanf("%lld %lld",&n,&m);
    for(ll i=1;i<=m;i++)
    {
        if(judge(i))a[i]=a[i-1]+1;
        else a[i]=a[i-1];
    }
    //1~m的遍历

    for(ll i=1;i<=n;i++)
    {
        scanf("%lld %lld",&l,&r);
        if(l>m||r>m||l<1||r<1){printf("Crossing the line\n");}
        else printf("%lld\n",a[r]-a[l-1]);
    }//输入输出完事儿~
    return 0;
}