結果
問題 |
No.1659 Product of Divisors
|
ユーザー |
![]() |
提出日時 | 2025-03-20 20:29:12 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,131 bytes |
コンパイル時間 | 191 ms |
コンパイル使用メモリ | 82,596 KB |
実行使用メモリ | 60,064 KB |
最終ジャッジ日時 | 2025-03-20 20:30:02 |
合計ジャッジ時間 | 4,626 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 7 TLE * 1 -- * 15 |
ソースコード
MOD = 10**9 + 7 def comb_mod(a, b): if b < 0 or b > a: return 0 if b == 0: return 1 numerator = 1 denominator = 1 for i in range(b): numerator = numerator * (a - i) % MOD denominator = denominator * (i + 1) % MOD return numerator * pow(denominator, MOD - 2, MOD) % MOD def lucas(n, k): if k == 0: return 1 a = n % MOD b = k % MOD if b > a: return 0 return (comb_mod(a, b) * lucas(n // MOD, k // MOD)) % MOD def factorize(n): factors = {} while n % 2 == 0: factors[2] = factors.get(2, 0) + 1 n //= 2 i = 3 while i * i <= n: while n % i == 0: factors[i] = factors.get(i, 0) + 1 n //= i i += 2 if n > 1: factors[n] = 1 return factors def solve(): N, K = map(int, input().split()) factors = factorize(N) if not factors: print(1) return result = 1 for p, e in factors.items(): n = e + K res = lucas(n, K) result = (result * res) % MOD print(result) if __name__ == "__main__": solve()