結果

問題 No.2211 Frequency Table of GCD
ユーザー HydruHydru
提出日時 2023-02-10 22:03:15
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,848 ms / 2,000 ms
コード長 881 bytes
コンパイル時間 532 ms
コンパイル使用メモリ 82,296 KB
実行使用メモリ 122,132 KB
最終ジャッジ日時 2024-07-07 16:18:28
合計ジャッジ時間 22,562 ms
ジャッジサーバーID
(参考情報)
judge5 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

def divisor_enumation(n):
i=1
result=set()
while(i*i<n):
if n%i==0:
result.add(i)
result.add(n//i)
i+=1
if i*i==n:
result.add(i)
return result
mod=998244353
n,m=map(int,input().split())
A=list(map(int,input().split()))
pow_2=[1]
for _ in range(n+1):
pow_2.append(pow_2[-1]*2%mod)
cnt=[0 for _ in range(m+1)]
for i in range(n):
a=A[i]
n=1
while(n*n<a):
if a%n==0:
cnt[n]+=1
cnt[a//n]+=1
n+=1
if n*n==a:
cnt[n]+=1
dem=[0 for _ in range(m+1)]
ans=[]
for i in range(m,0,-1):
ans.append((pow_2[cnt[i]]-1-dem[i])%mod)
if cnt[i]==0:
continue
X=divisor_enumation(i)
for u in X:
if u==i:
continue
dem[u]+=pow_2[cnt[i]]-1-dem[i]
dem[u]%=mod
for x in ans[::-1]:
print(x)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0