結果

問題 No.3045 反復重み付き累積和
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 13:11:02
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 795 bytes
コンパイル時間 252 ms
コンパイル使用メモリ 82,532 KB
実行使用メモリ 132,768 KB
最終ジャッジ日時 2025-06-12 13:13:48
合計ジャッジ時間 8,566 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 WA * 2
other WA * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

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

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    M = int(input[1])
    
    if M == 0:
        print(N)
        return
    
    primes = sieve(1500000)
    if len(primes) < M:
        print(0)
        return
    
    primes_subset = primes[:M]
    
    product = 1.0
    for p in primes_subset:
        product *= (p - 1) / p
    
    result = N * product
    print(math.floor(result))

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