結果

問題 No.2903 A Round-the-World Trip with the Tent
ユーザー 👑 獅子座じゃない人獅子座じゃない人
提出日時 2024-09-15 00:39:44
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,308 bytes
コンパイル時間 185 ms
コンパイル使用メモリ 82,360 KB
実行使用メモリ 340,088 KB
最終ジャッジ日時 2024-09-27 19:30:34
合計ジャッジ時間 3,687 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
59,956 KB
testcase_01 AC 35 ms
52,940 KB
testcase_02 TLE -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #

#using ChatGPT o1-preview

mod = 998244353

def compute_mobius(N):
    mu = [1] * (N + 1)
    is_prime = [True] * (N + 1)
    for i in range(2, N + 1):
        if is_prime[i]:
            for j in range(i, N + 1, i):
                is_prime[j] = False
                mu[j] *= -1
            i_squared = i * i
            for j in range(i_squared, N + 1, i_squared):
                mu[j] = 0
    return mu

def compute_divisors(N):
    divisors = [[] for _ in range(N + 1)]
    for i in range(1, N + 1):
        for j in range(i, N + 1, i):
            divisors[j].append(i)
    return divisors

def main():
    def solve():
        K_str, N_str = input().split()
        K = int(K_str)
        N = int(N_str)
        mu = compute_mobius(N)
        divisors = compute_divisors(N)
        pow2 = [1] * (N + 1)
        for i in range(1, N + 1):
            pow2[i] = (pow2[i - 1] * 2) % mod
        P = [0] * (N + 1)
        if N == 1:
            P[1] = 2 if K == 1 else 3
        else:
            for n in range(2, N + 1):
                total = 0
                for d in divisors[n]:
                    if mu[n // d] == 0:
                        continue
                    total = (total + mu[n // d] * pow2[d]) % mod
                P[n] = total % mod
        print(P[N] % mod)
    solve()
main()
0