結果
問題 | No.890 移調の限られた旋法 |
ユーザー |
![]() |
提出日時 | 2019-09-20 22:34:25 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 89 ms / 2,000 ms |
コード長 | 782 bytes |
コンパイル時間 | 174 ms |
コンパイル使用メモリ | 82,304 KB |
実行使用メモリ | 84,100 KB |
最終ジャッジ日時 | 2024-09-14 18:29:51 |
合計ジャッジ時間 | 3,447 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
from itertools import productN, K = map(int, input().split())MOD = 10**9 + 7fact = [1]*(N+1)rfact = [1]*(N+1)r = 1for i in range(1, N+1):fact[i] = r = r * i % MODrfact[N] = r = pow(fact[N], MOD-2, MOD)for i in range(N, 0, -1):rfact[i-1] = r = r * i % MODdef comb(n, k):return fact[n] * rfact[k] * rfact[n-k] % MODp = [1]*(N+1)p[0] = p[1] = 0vs = []ans = 0for x in range(2, N+1):if p[x] and N % x == 0 and K % x == 0:for y in range(x*x, N+1, x):p[y] = 0vs.append(x)L = len(vs)for ps in product([0, 1], repeat=L):e = 1c = 0for p, v in zip(ps, vs):if p:c ^= 1e *= vif e == 1:continueans += comb(N//e, K//e) if c else -comb(N//e, K//e)print(ans % MOD)