結果

問題 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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 TLE * 1
other -- * 42
権限があれば一括ダウンロードができます

ソースコード

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