結果
問題 | No.890 移調の限られた旋法 |
ユーザー | neterukun |
提出日時 | 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 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 650 ms
145,804 KB |
testcase_01 | AC | 652 ms
143,948 KB |
testcase_02 | AC | 646 ms
144,400 KB |
testcase_03 | AC | 646 ms
144,636 KB |
testcase_04 | AC | 646 ms
144,676 KB |
testcase_05 | AC | 649 ms
145,152 KB |
testcase_06 | AC | 650 ms
143,872 KB |
testcase_07 | AC | 682 ms
144,144 KB |
testcase_08 | AC | 654 ms
144,420 KB |
testcase_09 | AC | 648 ms
144,672 KB |
testcase_10 | AC | 651 ms
143,948 KB |
testcase_11 | AC | 646 ms
144,528 KB |
testcase_12 | AC | 679 ms
144,128 KB |
testcase_13 | AC | 661 ms
145,804 KB |
testcase_14 | AC | 664 ms
144,000 KB |
testcase_15 | AC | 654 ms
144,228 KB |
testcase_16 | AC | 648 ms
145,116 KB |
testcase_17 | AC | 651 ms
144,348 KB |
testcase_18 | AC | 671 ms
146,836 KB |
testcase_19 | AC | 658 ms
144,244 KB |
testcase_20 | AC | 653 ms
145,020 KB |
testcase_21 | AC | 656 ms
144,904 KB |
testcase_22 | AC | 646 ms
144,384 KB |
testcase_23 | AC | 652 ms
144,024 KB |
testcase_24 | AC | 652 ms
144,216 KB |
testcase_25 | AC | 647 ms
144,128 KB |
testcase_26 | AC | 650 ms
145,228 KB |
testcase_27 | AC | 660 ms
144,128 KB |
testcase_28 | AC | 647 ms
144,420 KB |
testcase_29 | AC | 644 ms
145,392 KB |
testcase_30 | AC | 653 ms
146,272 KB |
testcase_31 | AC | 648 ms
146,028 KB |
testcase_32 | AC | 650 ms
146,560 KB |
testcase_33 | AC | 659 ms
146,024 KB |
testcase_34 | AC | 647 ms
145,128 KB |
ソースコード
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 = MOD def 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 0 return (self.fact[k] * self.inv_fact[r]) % self.MOD def combination(self, k, r): """kCrを求める O(1)""" if k < r: return 0 return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD def 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 divisors def gcd(a, b): """a, bの最大公約数(greatest common divisor:GCD)を求める""" if b == 0: return a return gcd(b, a%b) n, k = map(int, input().split()) MOD = 10**9 + 7 comb = 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: continue total = n // num selected = k // num tmp = comb.combination(total, selected) li.append(num) memo[num] = tmp li = 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]] %= MOD ans = 0 for i in memo: ans += memo[i] ans %= MOD print(ans)