結果
問題 | No.890 移調の限られた旋法 |
ユーザー |
![]() |
提出日時 | 2024-09-30 04:21:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 508 ms / 2,000 ms |
コード長 | 551 bytes |
コンパイル時間 | 330 ms |
コンパイル使用メモリ | 82,372 KB |
実行使用メモリ | 201,248 KB |
最終ジャッジ日時 | 2024-09-30 04:21:46 |
合計ジャッジ時間 | 9,165 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
n,k=map(int,input().split()) if n==k: print(int(n>1)) exit() M=10**9+7 fa=[1,1] fb=[1,1] for i in range(2,n+1): fa+=[fa[-1]*i%M] fb+=[fb[-1]*(M//i)*fb[M%i]*fa[M%i-1]*(-1)%M] c=lambda n,k:fa[n]*fb[k]*fb[n-k]%M if n>=k else 0 q=[0]*(n+1) for i in range(2,n+1): if n%i==0 and k%i==0: q[i]=c(n//i,k//i) l=n P=[1]*(l+1) for i in range(2,l+1): if P[i]: for j in range(i+i,l+1,i): P[j]=0 P=[i for i in range(2,l+1) if P[i]] for p in P: for i in range(2,n+1): if i*p<=n: q[i]-=q[i*p] else: break print(sum(q)%M)