結果
問題 | No.890 移調の限られた旋法 |
ユーザー |
![]() |
提出日時 | 2019-09-20 23:09:24 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 742 ms / 2,000 ms |
コード長 | 921 bytes |
コンパイル時間 | 176 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 89,472 KB |
最終ジャッジ日時 | 2024-09-14 19:53:54 |
合計ジャッジ時間 | 26,970 ms |
ジャッジサーバーID (参考情報) |
judge6 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
N,K=map(int,input().split())mod=10**9+7import mathdef fact(x):L=int(math.sqrt(x))FA=dict()for i in range(2,L+2):while x%i==0:FA[i]=FA.get(i,0)+1x=x//iif x!=1:FA[x]=FA.get(x,0)+1return FAFACT=[1]for i in range(1,10**6+1):FACT.append(FACT[-1]*i%mod)FACT_INV=[pow(FACT[-1],mod-2,mod)]for i in range(10**6,0,-1):FACT_INV.append(FACT_INV[-1]*i%mod)FACT_INV.reverse()def Combi(a,b):if 0<=b<=a:return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%modelse:return 0F1=fact(N)F2=fact(K)LIST=[]for f in F1:if f in F2:LIST.append(f)ANS=0count=1from itertools import combinationsfor i in range(1,len(LIST)+1):L=list(combinations(LIST,i))for l in L:x=1for ls in l:x*=lsANS=(ANS+Combi(N//x,K//x)*count)%modcount*=-1print(ANS)