問題一覧 > 通常問題

No.2846 Birthday Cake

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 49
作問者 : 👑 AngrySadEight / テスター : Ayuna torisasami4
お気に入りにしたユーザー ProblemId : 11101 / 自分の提出
問題文最終更新日: 2024-07-15 23:32:48
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 441 (順位表) の他の問題:

Problem Statement

Here is $1$ circular birthday cake. $K$ people will cut this cake into sectors and eat it.

When cutting the cake, the share per $1$ person must be expressible as $\frac{1}{n}$ using an integer $n$ satisfying $1 \leq n \leq N$. Also, the sum of everyone's shares must be $1$ (that is, no cake may be left over).

Find the number of ways to cut the cake that satisfy the conditions. Here, two ways of cutting the cake are distinguished if there exists a person whose share of the cake differs between them.

Under the constraints of this problem, the answer is guaranteed to be less than $2^{60}$.

Constraints

  • All input values are integers.
  • $1 \leq K \leq N \leq 24$

Input

The input is given from Standard Input in the following format.

$K$ $N$

Output

Output the number of ways to cut the cake.

Sample

Sample 1
Input
3 4
Output
4

Denoting by $(g_1, g_2, g_3)$ the way of cutting in which the shares of the $1$-st, $2$-nd, and $3$-rd persons are $g_1, g_2, g_3$ respectively, the desired ways of cutting are the following $4$: $(\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})$.

In particular, note that the last $3$ are distinguished from one another.

Sample 2
Input
4 10
Output
47

Sample 3
Input
15 24
Output
4048971290390

Note that the answer may not fit in a $32$ bit integer type.

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