結果
問題 |
No.890 移調の限られた旋法
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:23:46 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 73 ms / 2,000 ms |
コード長 | 1,578 bytes |
コンパイル時間 | 285 ms |
コンパイル使用メモリ | 82,100 KB |
実行使用メモリ | 76,728 KB |
最終ジャッジ日時 | 2025-03-31 17:24:13 |
合計ジャッジ時間 | 3,696 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 |
ソースコード
import sys from itertools import combinations MOD = 10**9 + 7 max_fact = 10**6 # Precompute up to 1e6 # Precompute factorial and inverse factorial modulo MOD fact = [1] * (max_fact + 1) for i in range(2, max_fact + 1): fact[i] = fact[i-1] * i % MOD inv_fact = [1] * (max_fact + 1) inv_fact[max_fact] = pow(fact[max_fact], MOD-2, MOD) for i in range(max_fact - 1, 0, -1): inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD def comb(n, k): if k < 0 or k > n: return 0 return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD def factorize(n): factors = [] i = 2 while i * i <= n: if n % i == 0: factors.append(i) while n % i == 0: n //= i i += 1 if n > 1: factors.append(n) return factors def main(): N, K = map(int, sys.stdin.readline().split()) primes = factorize(N) primes = list(set(primes)) # Ensure unique primes divisors = [] for l in range(1, len(primes) + 1): for subset in combinations(primes, l): d = 1 for p in subset: d *= p if d > 1: mu = (-1) ** l divisors.append((d, mu)) sum_val = 0 for d, mu in divisors: if N % d != 0: continue m = N // d if K % d != 0: continue k = K // d if k < 0 or k > m: continue c = comb(m, k) sum_val = (sum_val + mu * c) % MOD ans = (-sum_val) % MOD print(ans) if __name__ == "__main__": main()