AtCoder-ContextABC-084-D-2017like-Number

57次阅读

共计 1967 个字符,预计需要花费 5 分钟才能阅读完成。

本文章为原创文章,未经过允许不得转载
运行要求
运行时间限制: 2sec
内存限制: 1024MB
未经允许,不得许转载
原题链接

题目
如果有一个奇数 N,N 和 (N+1//2) 都是素数的话,N 为 2017 的相似数
现在给定 Q 次查询
第 i(1<=i<=Q)次查询, 第 i 次查询给定奇数 li,ri,求 li<=x<=ri 范围内,2017 相似数的 x 的个数

输入前提条件

  • 1<=Q<=100000
  • 1<=li<=ri<=100000
  • li,ri 为奇数
  • 所有的输入都为整数

输入
输入按照以下形式标准输入

Q
l1 r1
l2 r1
.
.
.
lQ rQ

输出
第 i 行输出,第 i 次查询的结果


例 1
输入

1
3 7

输出

2

3 和 ((3+1)/2) 都为素数,所以 3 为 2017 的相似数
5 和((5+1)/2) 都为素数,所以 5 为 2017 的相似数
7 虽然是素数,但是 5((7+1)/2) 不是素数,所以 7 不是 2017 的相似数
以上所述,查询 1 的结果为 2

例 2
输入

4
13 13
7 11
7 11
2017 2017

输出

1
0
0
1

注意 2017 也是 2017 的相似数

例 2
输入

6
1 53
13 91
37 55
19 51
73 91
13 49

输出

4
4
1
1
1
2

读懂题目
给定一个区间,在这个区间的所有素数当中,挑选出折半以后仍然是素数的数字

解题思路
首先我们要看到 li,ri 的最大值是 100000,最小值是 1
li,ri 决定了区间的左边界和右边界
所以区间的最大跨度是 1 到 100000

首先我们要找到这个区间里面的所有的素数
因为是代码竞技所以不能使用第三方的扩展包
我们手写素数生成器
具体的方法用到素数筛选法
英文叫 sieve of Eratosthenes


我们取一串区间,记住最少要从 2 开始。我们找出这串数字的最小的元素,这里为 2
先找出 2 的倍数,然后去掉它们


在从剩下的里面找第 1 个没有被遍历的元素,这里是 3
找出 3 的倍数,然后去掉它们


依此类推,找出 5 的倍数,去掉他们


有的时候,最小元素的倍数不存在了,那么什么都不用做


以这种方式可以找到所有的素数

但是有一点要注意的是,遍历结束的标志。
区间从 2 到某个地方的方
start 可以从区间的开头遍历到区间的结尾,但是如果区间很大的话,我们只需要遍历到区间的平方根的地方就好了
比如 2 -16 的话
我们只需要遍历到 2 -4
2-100 的话
我们只需要遍历到 2 -10

好,我们拿到了 1 -100000 的所有的素数

我们再次遍历一次 1 -100000,判断每一个数是不是 2017 的相似数
用累积和的求法,算出从 1 到遍历点 i 的相似数的个数

具体就是如果 i 为 2017 的相似数,
那么
1 到 i 的 2017 相似数的个数 = 1 到(i-1)的 2017 相似数的个数 + 1

具体就是如果 i 不是 2017 的相似数,
那么
1 到 i 的 2017 相似数的个数 = 1 到(i-1)的 2017 相似数的个数

最后对于区间 (li,ri) 内 2017 相似数的个数的统计 =
1 到 ri 的 2017 相似数的个数 – 1 到 (li-1) 的 2017 相似数的个数

代码

import math


def sushu(n):
    arr = []
    for i in range(2, n + 1):
        arr.append(i)

    limit = int(math.sqrt(n)) + 1

    prev = []
    while True:
        start = arr[0]
        prev.append(start)
        if start > limit:
            break
        brr = []
        for i in arr:
            if i % start != 0:
                brr.append(i)
        arr = brr

    prev.extend(arr)
    return prev


n = 100000
shushu = sushu(100000)

marks = []
for i in range(n + 1):
    marks.append(False)

for j in shushu:
    marks[j] = True

marks2 = []
result = []
for i in range(n + 1):
    if i % 2 == 0:
        marks2.append(False)
        if i == 0:
            result.append(0)
        else:
            result.append(result[i - 1])
    else:
        if marks[(i + 1) // 2] and marks[i]:
            marks2.append(True)
            result.append(result[i - 1] + 1)
        else:
            marks2.append(False)
            result.append(result[i - 1])

Q = int(input())

ARR = []

for i in range(Q):
    ARR.append(list(map(int, input().split())))

for i in range(Q):
    start = ARR[i][0]
    end = ARR[i][1]
    print(result[end] - result[start - 1])

总结
这道题考察了对素数的求法。运用素数筛选法可以求出某一个区间以内的所有的素数

另外考察了累积和的运用

※ 另外,我会在我的微信个人订阅号上推出一些文章,欢迎关注


正文完
 0