結果
問題 | No.1760 Setwise Coprime |
ユーザー |
![]() |
提出日時 | 2021-10-16 06:33:40 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 351 ms / 2,000 ms |
コード長 | 1,302 bytes |
コンパイル時間 | 458 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 96,000 KB |
最終ジャッジ日時 | 2025-01-03 12:50:03 |
合計ジャッジ時間 | 8,660 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
mod=998244353 def modpow(a,b): res=1 while b: if b%2: res*=a res%=mod a*=a a%=mod b//=2 return res def lcmconv(x): n=len(x) n-=1 for i in range(n,0,-1): for j in range(2*i,n+1,i): x[j]+=x[i] for i in range(1,n+1): x[i]*=x[i] x[i]%=mod for i in range(1,n+1): for j in range(2*i,n+1,i): x[j]-=x[i] for i in range(1,n+1): x[i]%=mod return x n=int(input()) mebius=[1 for i in range(n+1)] prime=[True for i in range(n+1)] prime[1]=False for i in range(1,n+1): if prime[i]==False: continue for j in range(2*i,n+1,i): prime[j]=False for i in range(1,n+1): if prime[i]==False: continue for j in range(i*i,n+1,i*i): mebius[j]=0 for j in range(i,n+1,i): mebius[j]*=-1 mebiussum=0 for i in range(1,n+1): mebius[i]%=mod mebiussum+=mebius[i] mebiussum%=mod ans=0 ans+=mebiussum*mebiussum ans%=mod twosum=0 for i in range(1,n+1): twosum+=modpow(2,n//i)*mebius[i] twosum%=mod ans-=2*twosum*mebiussum ans%=mod x=[0 for i in range(n+1)] for i in range(1,n+1): x[i]=modpow(2,n//i)*mebius[i] x[i]%=mod x=lcmconv(x) twosum*=twosum twosum%=mod for i in range(1,n+1): twosum-=x[i] twosum%=mod ans+=twosum z=3*modpow(4,mod-2)%mod for i in range(1,n+1): ans+=x[i]*modpow(z,n//i) ans%=mod print(ans)