結果

問題 No.3045 反復重み付き累積和
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:01:50
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,209 bytes
コンパイル時間 201 ms
コンパイル使用メモリ 82,572 KB
実行使用メモリ 62,316 KB
最終ジャッジ日時 2025-06-12 13:07:58
合計ジャッジ時間 3,742 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 3
other WA * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math

def sieve(n):
    sieve = [True] * (n + 1)
    sieve[0] = sieve[1] = False
    for i in range(2, int(math.sqrt(n)) + 1):
        if sieve[i]:
            sieve[i*i : n+1 : i] = [False] * len(sieve[i*i : n+1 : i])
    primes = [i for i, is_prime in enumerate(sieve) if is_prime]
    return primes

def main():
    N, M = map(int, sys.stdin.readline().split())
    
    # Estimate the upper bound for the M-th prime
    if M == 0:
        print(N)
        return
    if M <= 6:
        limit = 15  # For small M, use a small limit
    else:
        # Approximate the M-th prime using prime number theorem
        approx = M * (math.log(M) + math.log(math.log(M)))
        limit = int(approx) * 2  # Double to ensure coverage
    
    primes = sieve(limit)
    while len(primes) < M:
        # If sieve didn't find enough primes, increase the limit and try again
        limit *= 2
        primes = sieve(limit)
    
    primes = primes[:M]
    product = 1
    for p in primes:
        if p > N:
            print(0)
            return
        if product > N // p:
            print(0)
            return
        product *= p
    print(N // product)

if __name__ == '__main__':
    main()
0