No.2846 Birthday Cake
タグ : / 解いたユーザー数 44
作問者 : 👑
AngrySadEight
/ テスター :
Ayuna
torisasami4
問題文
ここに，$1$ 個の円形をした誕生日ケーキがあります．このケーキを，$K$ 人で扇形状に切り分けて食べることにしました．
ケーキを切り分ける際には，$1$ 人あたりの取り分が，$1 \leq n \leq N$ を満たす整数 $n$ を用いて，$\frac{1}{n}$ と表される必要があります．また，全員のケーキの取り分の総和は $1$ となる必要があります（すなわちケーキは余らせてはなりません）．
条件を満たすケーキの切り分け方の個数を求めてください．ただし，ケーキの切り分け方は，ある人が存在して，その人のケーキの取り分が異なる場合に区別されます．
なお，この問題の制約下において，答えは $2^{60}$ 未満になることが保証されます．
制約
- 入力は全て整数である．
- $1 \leq K \leq N \leq 24$
入力
入力は以下の形式で標準入力から与えられる．
$K$ $N$
出力
ケーキの切り分け方の個数を出力せよ．
サンプル
サンプル1
入力
3 4
出力
4
$1$ 人目，$2$ 人目，$3$ 人目の取り分がそれぞれ $g_1, g_2, g_3$ であるような分け方を $(g_1, g_2, g_3)$ と表すとき，求める分け方は $(\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})$ の $4$ 個です．
特に，後ろの $3$ 個が区別されることに注意してください．
サンプル2
入力
4 10
出力
47
サンプル3
入力
15 24
出力
4048971290390
答えは $32$ bit 型の整数値に収まらない可能性があることに注意してください．
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。