1. 题目

传送门= ̄ω ̄=

2. 题解

好吧我承认我把这题写复杂了QvQ

KB又把这题秒杀了Orz

但还是很有意思的QvQ

蒟蒻我写的是扩展埃氏筛

复杂度约为$O(L^{0.7}+R^{0.7})$

并且不需要$R-L≤1000000$这个条件

(也就是说题目把$R$开到$10^{10}$并且$L$任取一个小于$R$的数都是可以过的,只要把数组开大就行了)

空间复杂度是$O(\sqrt R)$的

具体看代码注释吧QvQ

/*
 * 素数密度.cpp
 * This file is part of 素数密度
 *
 * Copyright (C) 2018 - xzy
 *
 * 素数密度 is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * 素数密度 is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with 素数密度. If not, see <http://www.gnu.org/licenses/>.
 */


#include <bits/stdc++.h>

#define SQS (50000)//sqrt(R)的范围

using namespace std;

int pre[SQS], suf[SQS];

//设sum[i]表示区间[1,i]的素数个数,那么:
//pre[i]=sum[i],suf[i]=sum[x/i],x是下面这个函数的参数x
//这样设状态是为了节省空间,能让空间变为根号x的级别

int E_Sieve(int x)//返回值为sum[x]
{
    if (x <= 1) return 0;//特判
    int sqx = sqrt(x);//计算sqrt(x)(根号x)
    for (int i = 1; i <= sqx; i += 1)//初始假设所有的数都是素数
        pre[i] = i - 1, suf[i] = x / i - 1;
    //下面开始筛去合数
    for (int p = 2; p <= sqx; p += 1)//枚举[2,sqrt(x)]内素数
    {
        if (pre[p] == pre[p - 1]) continue;//如果p不是质数就continue
        //扩展埃氏筛的转移式:f[i]-=f[i/p]-f[p-1]
        //这个转移式我就不在这说明了,属于算法内容,自行google吧(百度很难搜到的样子)
        int t = pre[p - 1];
        for (int i = 1; i <= sqx / p; i += 1)
            suf[i] -= suf[i * p] - t;
        for (int i = sqx / p + 1; i <= min(sqx, x / p / p); i += 1)
            suf[i] -= pre[x / i / p] - t;
        //上面这两个for都是筛去suf[1,sqx]中的合数的
        for (int i = sqx; i >= p * p; i -= 1)
            pre[i] -= pre[i / p] - t;
        //这个for是筛去pre[1,sqx]中的合数
    }
    return suf[1];//suf[1]=sum[x]
}

int L, R;

int main(int argc, char const* argv[])
{
    scanf("%d%d", &L, &R), printf("%d\n", E_Sieve(R) - E_Sieve(L - 1));//因为返回的是前缀和嘛,相减就是了
    return 0;
}

话说加上注释代码真丑,再发一遍没有注释的(我真无聊):

/*
 * 素数密度.cpp
 * This file is part of 素数密度
 *
 * Copyright (C) 2018 - xzy
 *
 * 素数密度 is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * 素数密度 is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with 素数密度. If not, see <http://www.gnu.org/licenses/>.
 */


#include <bits/stdc++.h>

#define SQS (50000)

using namespace std;

int pre[SQS], suf[SQS];

int E_Sieve(int x)
{
    if (x <= 1) return 0;
    int sqx = sqrt(x);
    for (int i = 1; i <= sqx; i += 1)
        pre[i] = i - 1, suf[i] = x / i - 1;
    for (int p = 2; p <= sqx; p += 1)
    {
        if (pre[p] == pre[p - 1]) continue;
        int t = pre[p - 1];
        for (int i = 1; i <= sqx / p; i += 1)
            suf[i] -= suf[i * p] - t;
        for (int i = sqx / p + 1; i <= min(sqx, x / p / p); i += 1)
            suf[i] -= pre[x / i / p] - t;
        for (int i = sqx; i >= p * p; i -= 1)
            pre[i] -= pre[i / p] - t;
    }
    return suf[1];
}

int L, R;

int main(int argc, char const* argv[])
{
    scanf("%d%d", &L, &R), printf("%d\n", E_Sieve(R) - E_Sieve(L - 1));
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *