問題一覧 > 通常問題

No.2846 Birthday Cake

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 45
作問者 : 👑 AngrySadEightAngrySadEight / テスター : AyunaAyuna torisasami4torisasami4
3 ProblemId : 11101 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-07-15 23:32:48

問題文

ここに,11 個の円形をした誕生日ケーキがあります.このケーキを,KK 人で扇形状に切り分けて食べることにしました.

ケーキを切り分ける際には,11 人あたりの取り分が,1nN1 \leq n \leq N を満たす整数 nn を用いて,1n\frac{1}{n} と表される必要があります.また,全員のケーキの取り分の総和は 11 となる必要があります(すなわちケーキは余らせてはなりません).

条件を満たすケーキの切り分け方の個数を求めてください.ただし,ケーキの切り分け方は,ある人が存在して,その人のケーキの取り分が異なる場合に区別されます.

なお,この問題の制約下において,答えは 2602^{60} 未満になることが保証されます.

制約

  • 入力は全て整数である.
  • 1KN241 \leq K \leq N \leq 24

入力

入力は以下の形式で標準入力から与えられる.

KK NN

出力

ケーキの切り分け方の個数を出力せよ.

サンプル

サンプル1
入力
3 4
出力
4

11 人目,22 人目,33 人目の取り分がそれぞれ g1,g2,g3g_1, g_2, g_3 であるような分け方を (g1,g2,g3)(g_1, g_2, g_3) と表すとき,求める分け方は (13,13,13),(12,14,14),(14,12,14),(14,14,12)(\frac{1}{3}, \frac{1}{3}, \frac{1}{3}), (\frac{1}{2}, \frac{1}{4}, \frac{1}{4}), (\frac{1}{4}, \frac{1}{2}, \frac{1}{4}), (\frac{1}{4}, \frac{1}{4}, \frac{1}{2})44 個です.

特に,後ろの 33 個が区別されることに注意してください.

サンプル2
入力
4 10
出力
47

サンプル3
入力
15 24
出力
4048971290390

答えは 3232 bit 型の整数値に収まらない可能性があることに注意してください.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。