結果

問題 No.1661 Sum is Prime (Hard Version)
ユーザー tamatotamato
提出日時 2021-08-27 23:08:17
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,196 bytes
コンパイル時間 212 ms
コンパイル使用メモリ 82,516 KB
実行使用メモリ 317,272 KB
最終ジャッジ日時 2024-05-01 04:01:10
合計ジャッジ時間 27,480 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 69 ms
77,024 KB
testcase_01 WA -
testcase_02 AC 2,219 ms
292,336 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 AC 73 ms
76,136 KB
testcase_07 AC 68 ms
75,920 KB
testcase_08 WA -
testcase_09 AC 66 ms
77,360 KB
testcase_10 AC 73 ms
75,876 KB
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 1,964 ms
291,096 KB
testcase_15 WA -
testcase_16 AC 2,173 ms
297,064 KB
testcase_17 AC 2,007 ms
290,824 KB
testcase_18 AC 932 ms
208,912 KB
testcase_19 AC 1,550 ms
274,680 KB
testcase_20 AC 876 ms
210,324 KB
testcase_21 AC 2,118 ms
292,412 KB
testcase_22 AC 2,096 ms
292,332 KB
testcase_23 TLE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from bisect import bisect

def prime_sieve(n):
    """
    Efficient prime sieve, due to Robert William Hanks.
    Source: http://stackoverflow.com/a/2068548
    """
    sieve = [True] * (n//2)
    for i in range(3,int(n**0.5)+1,2):
        if sieve[i//2]:
            sieve[i*i//2::i] = [False] * ((n-i*i-1)//(2*i)+1)
    return [2] + [2*i+1 for i in range(1,n//2) if sieve[i]]

"""
Limit controls the number of primes that are sieved
to cache small values of pi(x).  Without caching,
runtime will be exponential.
When computing pi(x), limit should be
at least sqrt(x).  A higher value of limit
that caches more values can sometimes improve performance.
"""

limit = 10**6
primes = prime_sieve(limit)

phi_cache = {}
def phi(x, a):
    """
    Implementation of the partial sieve function, which
    counts the number of integers <= x with no prime factor less
    than or equal to the ath prime.
    """
    # If value is cached, just return it
    if (x, a) in phi_cache: return phi_cache[(x, a)]

    # Base case: phi(x, a) is the number of odd integers <= x
    if a == 1: return (x + 1) // 2

    result = phi(x, a-1) - phi(x // primes[a-1], a-1)
    phi_cache[(x, a)] = result # Memoize
    return result


pi_cache = {}
def pi(x):
    """
    Computes pi(x), the number of primes <= x, using
    the Meissel-Lehmer algorithm.
    """
    # If value is cached, return it
    if x in pi_cache: return pi_cache[x]

    # If x < limit, calculate pi(x) using a bisection
    # algorithm over the sieved primes.
    if x < limit:
        result = bisect(primes, x)
        pi_cache[x] = result
        return result

    a = pi(int(x ** (1./4)))
    b = pi(int(x ** (1./2)))
    c = pi(int(x ** (1./3)))

    # This quantity must be integral,
    # so we can just use integer division.
    result = phi(x,a) + (b+a-2) * (b-a+1) // 2

    for i in range(a+1, b+1):
        w = x // primes[i-1]
        b_i = pi(w ** (1./2))
        result = result - pi(w)
        if i <= c:
            for j in range(i, b_i+1):
                result = result - pi(w // primes[j-1]) + j - 1
    pi_cache[x] = result
    return result

L, R = map(int, input().split())
print(pi(R) - pi(L) + pi(2*R-1) - pi(2*L))
0