結果
問題 | No.890 移調の限られた旋法 |
ユーザー |
![]() |
提出日時 | 2019-09-21 11:32:50 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 682 ms / 2,000 ms |
コード長 | 2,050 bytes |
コンパイル時間 | 166 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 146,836 KB |
最終ジャッジ日時 | 2024-09-17 14:56:19 |
合計ジャッジ時間 | 24,620 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
class Combination:'''MOD上の計算量:階乗・逆元テーブルの作成O(N)nCkを求めるO(1)'''def __init__(self, n, MOD):self.fact = [1]for i in range(1, n + 1):self.fact.append(self.fact[-1] * i % MOD)self.inv_fact = [pow(self.fact[i], MOD - 2, MOD) for i in range(n + 1)]self.MOD = MODdef factorial(self, k):"""k!を求める O(1)"""return self.fact[k]def inverse_factorial(self, k):"""k!の逆元を求める O(1)"""return self.inv_fact[k]def permutation(self, k, r):"""kPrを求める O(1)"""if k < r:return 0return (self.fact[k] * self.inv_fact[r]) % self.MODdef combination(self, k, r):"""kCrを求める O(1)"""if k < r:return 0return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MODdef make_divisors(n):"""自然数nの約数を列挙したリストを出力する計算量: O(sqrt(N))入出力例: 12 -> [1, 2, 3, 4, 6, 12]"""divisors = []for k in range(1, int(n**0.5) + 1):if n % k == 0:divisors.append(k)if k != n // k:divisors.append(n // k)divisors = sorted(divisors)return divisorsdef gcd(a, b):"""a, bの最大公約数(greatest common divisor:GCD)を求める"""if b == 0:return areturn gcd(b, a%b)n, k = map(int, input().split())MOD = 10**9 + 7comb = Combination(10**6 + 10, MOD)gcd_nk = gcd(n, k)div_list = make_divisors(gcd_nk)li = []memo = {}for num in div_list:if num == 1:continuetotal = n // numselected = k // numtmp = comb.combination(total, selected)li.append(num)memo[num] = tmpli = li[::-1]for i in range(len(li)):for j in range(i):if li[j] % li[i] == 0:memo[li[i]] -= memo[li[j]]memo[li[i]] %= MODans = 0for i in memo:ans += memo[i]ans %= MODprint(ans)