結果
問題 | No.2211 Frequency Table of GCD |
ユーザー |
![]() |
提出日時 | 2023-02-10 22:02:44 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 425 ms / 2,000 ms |
コード長 | 1,240 bytes |
コンパイル時間 | 144 ms |
コンパイル使用メモリ | 82,284 KB |
実行使用メモリ | 107,908 KB |
最終ジャッジ日時 | 2024-07-07 18:00:34 |
合計ジャッジ時間 | 8,727 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
import sysinput = sys.stdin.readlineN,M=map(int,input().split())A=list(map(int,input().split()))# エラトステネスの篩を用いた素因数分解・約数列挙MAX=3*10**5+10 # 使いたい最大値を指定# Sieve[i]で、iの最も小さい約数を返す。Sieve=[i for i in range(MAX)]for i in range(2,MAX):if Sieve[i]!=i:continuefor j in range(i,MAX,i):if Sieve[j]==j:Sieve[j]=i# 素因数分解def fact(x):D=dict()while x!=1:k=Sieve[x]if k in D:D[k]+=1else:D[k]=1x//=kreturn D# 約数列挙def faclist(x):LIST=[1]while x!=1:k=Sieve[x]count=0while x%k==0:count+=1x//=kLIST2=[]for l in LIST:for i in range(1,count+1):LIST2.append(l*k**i)LIST+=LIST2return LISTmod=998244353ANS=[0]*(M+1)for a in A:for x in faclist(a):ANS[x]+=1ANS2=[pow(2,a,mod)-1 for a in ANS]for i in range(M,0,-1):k=ANS2[i]for u in faclist(i):if i==u:continueANS2[u]-=kANS2[i]%=modprint("\n".join(map(str,ANS2[1:])))