備忘録
問題
回答
import sys, os, math, bisect, itertools, collections, heapq, queue from decimal import Decimal # import fractions sys.setrecursionlimit(10000000) ii = lambda: int(sys.stdin.buffer.readline().rstrip()) il = lambda: list(map(int, sys.stdin.buffer.readline().split())) fl = lambda: list(map(float, sys.stdin.buffer.readline().split())) iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)] iss = lambda: sys.stdin.buffer.readline().decode().rstrip() sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split())) isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)] lcm = lambda x, y: (x * y) // math.gcd(x, y) # lcm = lambda x, y: (x * y) // fractions.gcd(x, y) MOD = 10 ** 9 + 7 MAX = float('inf') def main(): if os.getenv("LOCAL"): sys.stdin = open("input.txt", "r") # エラトステネスの篩で、 # 2 から 10^5までの素数を列挙 limit = 10 ** 5 + 1 prime = [False if n % 2 == 0 or n % 3 == 0 or n % 5 == 0 else True for n in range(limit)] prime[0] = prime[1] = False prime[2] = prime[3] = prime[5] = True for p in range(3, limit, 2): if math.sqrt(limit) < p: break for q in range(p ** 2, limit, p): prime[q] = False # 累積和 # 2017に似た数字の数を求めておく cnt = [0] * limit for n in range(len(cnt)): if prime[n] and prime[(n + 1) // 2]: cnt[n] = 1 for n in range(1, len(cnt)): cnt[n] += cnt[n - 1] # 回答 Q = ii() for q in range(Q): l, r = il() print(cnt[r] - cnt[l - 1]) if __name__ == '__main__': main()
考え方
素数に関する問題。
エラトステネスの篩で条件に一致する素数を予め列挙しておき、
O(1)
で回答を出力する。
要素数を10^5
個持った配列を用意し、
value
がTrue
の時index
が素数、False
の時index
が非素数とする。
配列を用意する際にはあらかじめ2, 3, 5
の倍数は非素数としておき、
2, 3, 5
は素数としておく。
その後、エラトステネスの篩を用いて3
以降の奇数に対して
素数か否かを探索しておく。
(2
の倍数、つまり偶数は既に非素数としているため)
0
から10^5
までの素数の列挙ができたら、
全ての素数に対して条件に一致するか否か(2017に似た数か)を探索しておき、
探索結果からi
番目までの2017の数を累積和で予め数えておく。
累積和を使用して、i
番目までの条件に一致する素数の数を数えておくことによって、
r番目までの条件に一致する素数 - l番目までの条件に一致する素数
とO(1)
で回答を得ることが出来る。