結果
問題 |
No.2211 Frequency Table of GCD
|
ユーザー |
![]() |
提出日時 | 2023-02-10 23:50:14 |
言語 | PyPy3 (7.3.15) |
結果 |
RE
|
実行時間 | - |
コード長 | 770 bytes |
コンパイル時間 | 497 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 111,360 KB |
最終ジャッジ日時 | 2024-07-07 17:39:26 |
合計ジャッジ時間 | 4,179 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 3 |
other | RE * 26 |
ソースコード
#模範解答 def prime_factors(n):#2~nまでの数を素因数分解して、各々の素因数リストを返します。O(nlog(n)) d=[[] for _ in range(n+1)] for i in range(1,n+1): for j in range(i,n+1,i): d[j].append(i) return(d) N,M=map(int,input().split()) mod=998244353 A=list(map(int,input().split())) ans=[0]*(M+1)#ans[i]:最大公約数がi ans_ex=[0]*(M+1)#ans_ex[i]:最大公約数がiの倍数 num=[0]*(M+1) for i in range(N): for n in d[A[i]]: num[n]+=1 for i in range(1,M+1): ans_ex[i]=pow(2,num[i],mod)-1 for i in range(M,0,-1): ima=ans_ex[i]%mod ima_ind=2*i while ima_ind<=M: ima-=ans[ima_ind] ima_ind+=i ima%=mod ans[i]=ima for i in range(1,M+1): print(ans[i])