結果

問題 No.1727 [Cherry 3rd Tune] Stray
コンテスト
ユーザー 👑 Kazun
提出日時 2021-08-15 18:04:40
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 727 bytes
コンパイル時間 231 ms
コンパイル使用メモリ 82,152 KB
実行使用メモリ 54,428 KB
最終ジャッジ日時 2024-10-07 08:48:00
合計ジャッジ時間 1,127 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

# Hard の想定解放

def Divisors(N):
    N=abs(N)
    L,U=[],[]
    k=1
    while k*k <=N:
        if N%k== 0:
            L.append(k)
            if k*k!=N:
                U.append(N//k)
        k+=1
    return L+U[::-1]

#==================================================
from math import gcd
#N,C=map(int,input().split())
N=int(input())
C=2

Mod=998244353

# gcd(N,x) の分布を調べる.
D=Divisors(N)[::-1]; M=len(D)
H={}

for i in range(M):
    d=D[i]
    H[d]=N//d
    for j in range(i):
        e=D[j]
        if e%d==0:
            H[d]-=H[e]

# σ^k 型の計算
A=0
for g in H:
    m=2*g
    A+=H[g]*pow(C,m,Mod); A%=Mod

# τ σ^k 型の計算
B=N*pow(C,N,Mod)

X=(A+B)*pow(2*N,Mod-2,Mod)
X%=Mod

print(X)
0