結果
問題 | No.2365 Present of good number |
ユーザー |
![]() |
提出日時 | 2023-07-11 07:07:46 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 107 ms / 2,000 ms |
コード長 | 939 bytes |
コンパイル時間 | 168 ms |
コンパイル使用メモリ | 7,424 KB |
実行使用メモリ | 12,928 KB |
最終ジャッジ日時 | 2024-09-13 00:01:51 |
合計ジャッジ時間 | 5,743 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 39 |
コンパイルメッセージ
Syntax OK
ソースコード
require 'prime'N, K = gets.split.map(&:to_i)MOD = 10 ** 9 + 7def ff(a, k)return a if k <= 0nums = a.prime_divisionres = 1nums.each do |v, e|res *= (v + 1).pow(e)endff(res, k - 1)enddef f(a, k)return a if k <= 0nums = a.prime_divisionif nums.last[0] <= 3 && nums.size == 2cnt_2 = nums[0][1]cnt_3 = nums[1][1]d = k / 2cnt_2 = (cnt_2 * 2.pow(d, MOD - 1)) % (MOD - 1)cnt_3 = (cnt_3 * 2.pow(d, MOD - 1)) % (MOD - 1)if k % 2 != 0cnt_2, cnt_3 = 2 * cnt_3, cnt_2endreturn (2.pow(cnt_2, MOD) * 3.pow(cnt_3, MOD)) % MODelsif nums.last[0] == 2cnt = nums[0][1]d = k / 2cnt = (cnt * 2.pow(d, MOD - 1)) % (MOD - 1)if k % 2 == 0return 2.pow(cnt, MOD)elsereturn 3.pow(cnt, MOD)endendres = 1nums.each do |v, e|res *= (v + 1).pow(e)endf(res, k - 1)end# pp ff(N, K) % MODpp f(N, K) % MOD