結果
問題 | No.2120 場合の数の下8桁 |
ユーザー |
|
提出日時 | 2022-11-04 23:03:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 717 ms / 2,000 ms |
コード長 | 556 bytes |
コンパイル時間 | 301 ms |
コンパイル使用メモリ | 82,432 KB |
実行使用メモリ | 246,216 KB |
最終ジャッジ日時 | 2024-07-18 20:57:56 |
合計ジャッジ時間 | 5,921 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
m = int(input())n = int(input())if n > m:print("0"*8)exit()mod = 10**8def e(n): #O(NloglogN)l = [i for i in range(n+1)]x = []for i in range(2,n+1):if l[i] == i:x.append(i)for p in range(i+i,n+1,i):l[p] = ireturn xp = e(m)d =[0]*(m+1)for pn in p:now = pncnt = 0while now <= m:cnt += m//now-(m-n)//nowcnt -= n//nownow *= pnd[pn] = cntans = 1for k,v in enumerate(d):if v == 0: continueans *= pow(k,v,mod)ans %= modans = str(ans)print("0"*(8-len(ans)) + ans)