結果
問題 | No.2829 GCD Divination |
ユーザー |
|
提出日時 | 2024-06-10 12:55:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 134 ms / 2,000 ms |
コード長 | 815 bytes |
コンパイル時間 | 321 ms |
コンパイル使用メモリ | 82,428 KB |
実行使用メモリ | 77,304 KB |
最終ジャッジ日時 | 2024-06-20 23:01:46 |
合計ジャッジ時間 | 3,663 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 35 |
ソースコード
from collections import defaultdict N=int(input()) factor=set() factor.add(1) factor.add(N) for i in range(2,int(N**0.5)+3): if N%i==0: factor.add(i) factor.add(N//i) factor=sorted(list(factor)) def calc_gcd(N): f=set() for i in range(1,int(N**0.5)+3): if N%i==0: f.add(i) f.add(N//i) f=list(reversed(sorted(list(f)))) cnt=defaultdict(int) ans=[] for j in range(len(f)): cnt[f[j]]=N//f[j] for k in range(j): if f[k]%f[j]==0: cnt[f[j]]-=cnt[f[k]] ans.append((f[j],cnt[f[j]])) return ans dp=defaultdict(int) for i in factor: if i==1: continue array=calc_gcd(i) d=0 for j in range(len(array)): p,cnt=array[j] if p==i: continue d+=((cnt/i)*dp[p]) #print(p) d+=1 d=(d*i)/(i-1) dp[i]=d #print(dp) print(dp[N])