結果
問題 |
No.1809 Divide NCK
|
ユーザー |
|
提出日時 | 2022-01-14 22:33:08 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 53 ms / 2,000 ms |
コード長 | 1,553 bytes |
コンパイル時間 | 178 ms |
コンパイル使用メモリ | 82,460 KB |
実行使用メモリ | 66,456 KB |
最終ジャッジ日時 | 2024-11-20 12:19:44 |
合計ジャッジ時間 | 3,530 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 39 |
ソースコード
from math import gcd import random from collections import defaultdict def is_prime(n): if n==2: return True if n==1 or n&1==0: return False d=(n-1)>>1 while d&1==0: d>>=1 for k in range(100): a=random.randint(1,n-1) t=d y=pow(a, t, n) while t!=n-1 and y!=1 and y!=n-1: y=(y*y)%n t<<=1 if y!=n-1 and t&1==0: return False return True def prime_fact(N): res=defaultdict(int) if N==1: return res p=2 while(p<=10**4 and N>1): if N%p==0: while(N%p==0): res[p]+=1 N//=p p+=1 while(N>1): if is_prime(N): res[N]+=1 break x=random.randrange(N) y=(x*x+1)%N i=1 while(True): d=gcd(abs(x-y),N) if d==1: i+=1 elif d==N: res[N]+=1 return res else: res[d]+=1 N//=d break x=(x*x+1)%N y=(y*y+1)%N y=(y*y+1)%N return res n, k, m = map(int,input().split()) def count(x, y): #1*2*...*xをyで割り切る回数 ret = 0 rui = 0 for i in range(65, -1, -1): now = x // (y ** i) ret += now rui += now return ret p = prime_fact(m) ans = 10 ** 18 for num, v in p.items(): now = count(n, num) - count(k, num) - count(n - k, num) ans = min(ans, now // v) print(ans)