結果
問題 | No.2120 場合の数の下8桁 |
ユーザー | 👑 Kazun |
提出日時 | 2022-11-04 22:17:32 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,077 bytes |
コンパイル時間 | 273 ms |
コンパイル使用メモリ | 87,104 KB |
実行使用メモリ | 184,868 KB |
最終ジャッジ日時 | 2023-09-26 00:44:29 |
合計ジャッジ時間 | 8,542 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 68 ms
71,400 KB |
testcase_01 | AC | 68 ms
71,508 KB |
testcase_02 | AC | 67 ms
71,584 KB |
testcase_03 | AC | 66 ms
71,280 KB |
testcase_04 | AC | 68 ms
71,396 KB |
testcase_05 | AC | 68 ms
71,636 KB |
testcase_06 | AC | 314 ms
184,704 KB |
testcase_07 | AC | 69 ms
71,524 KB |
testcase_08 | AC | 68 ms
71,508 KB |
testcase_09 | AC | 80 ms
76,696 KB |
testcase_10 | AC | 195 ms
125,976 KB |
testcase_11 | AC | 313 ms
184,340 KB |
testcase_12 | AC | 75 ms
75,968 KB |
testcase_13 | AC | 105 ms
77,620 KB |
testcase_14 | AC | 116 ms
78,712 KB |
testcase_15 | AC | 929 ms
125,632 KB |
testcase_16 | AC | 308 ms
180,228 KB |
testcase_17 | TLE | - |
testcase_18 | AC | 69 ms
71,456 KB |
testcase_19 | TLE | - |
ソースコード
def Smallest_Prime_Factor(N): """ 0,1,2,...,N の最小の素因数のリスト (0,1 については 1 にしている) """ if N<=1: return [1]*(N+1) T=[0]*(N+1); T[0]=T[1]=1 for i in range(2, N+1, 2): T[i]=2 for i in range(3, N+1, 6): T[i]=3 prime=[2,3] i=5; d=2 while i<=N: if T[i]==0: T[i]=i prime.append(i) for p in prime: if i*p<=N: T[i*p]=p else: break if p==T[i]: break i+=d; d=6-d return T #拡張ユークリッドの互除法 def Extend_Euclid(a: int, b: int): """ gcd(a,b) と ax+by=gcd(a,b) を満たす整数 x,y の例を挙げる. [Input] a,b: 整数 [Output] (x,y,gcd(a,b)) """ s,t,u,v=1,0,0,1 while b: q,a,b=a//b,b,a%b s,t=t,s-q*t u,v=v,u-q*v return s,u,a def Modulo_Inverse(a, m): """ (mod m) における逆元を求める. Args: a (int): mod m の元 m (int): 法 Returns: int: 可逆元が存在するならばその値, 存在しないのであれば -1 """ h=Extend_Euclid(a,m) return h[0]%m if h[2]==1 else -1 #================================================== def solve(): M=int(input()) N=int(input()) if M<N: return 0 N=min(N,M-N) Mod=10**8 L=Smallest_Prime_Factor(M) e2=0; e5=0; xi=1 for k in range(M,M-N,-1): while k>1: if L[k]==2: e2+=1 elif L[k]==5: e5+=1 else: xi=(xi*L[k])%Mod k//=L[k] f2=0; f5=0; yi=1 for k in range(1,N+1): while k>1: if L[k]==2: f2+=1 elif L[k]==5: f5+=1 else: yi=(yi*L[k])%Mod k//=L[k] return pow(2,e2-f2,Mod)*pow(5,e5-f5,Mod)*xi*Modulo_Inverse(yi,Mod)%Mod #================================================== print(str(solve()).zfill(8))