hackercupai/hackercup huggingface dataset:
First we need to determine how many bracelets Ishiko is going to exhibit. When \(N = K\) (that is, when all of the beads are green) there is of course just \(1\) bracelet to display. Otherwise, there are \(\frac{(N-1)!}{K!}\) ways to arrange \(N\) beads in a ring when \(K\) are green beads and the rest are unique colors. Since there's always at least \(1\) unique bead, we can say that that unique bead is in a fixed position in each bracelet.

Next, we observe that a display case of height \(H\) holds exactly \(H^2\) bracelets. The problem then is to determine the minimum number of perfect squares needed to sum to \(\frac{(N-1)!}{K!}\). According to [Lagrange's four-square theorem](https://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem), we will never need more than \(4\) squares, so Ishiko only needs at most \(4\) display cases.

Let \(X\) be the number of bracelets to be displayed. As \(X\) can be as large as \(1{,}000{,}000{,}000!\), we still need a quick way to determine whether the answer is \(1\), \(2\), \(3\), or \(4\). The answer is \(1\) if \(X\) is a square number, which is something we can determine from the prime factorization of \(X\). If every prime in the factorization appears an even number of times, then \(X\) is a square number.

[Legendre's formula](https://en.wikipedia.org/wiki/Legendre%27s_formula) gives us an easy way to compute the exponent on a given prime \(p\) in the factorization of \(n!\) by summing \(\lfloor n / p^i \rfloor\) for all \(i\), which is quick since \(i\) will never be larger than \(32\) for a \(32\)-bit integer. If \(a\) is the exponent on \(p\) in \(N-1!\), and \(b\) is the exponent on \(p\) in \(K\), then the exponent on \(p\) in \(\frac{(N-1!)}{K!}\) is just \(a - b\).

How can we tell if the answer is \(2\)? Why, we can just apply the aptly-named [two-square theorem](https://en.wikipedia.org/wiki/Sum_of_two_squares_theorem), which says that \(X\) can be represented as a sum of two squares if and only if its prime decomposition contains no factor \(p^k\), where \(p \equiv 3\ (\text{mod}\ 4)\) and \(k\) is odd. Since we already have the prime factorization of \(X\), this is easy to determine.

To determine if the answer is \(3\), we'll appeal to Legendre once more. [Legendre's three-square theorem](https://en.wikipedia.org/wiki/Legendre%27s_three-square_theorem) says that \(X\) can be represented as a sum of three squares as long as it is *not* of the form \(X = 4^a(8b + 7)\), for non-negative \(a\) and \(b\). We can check if \(X\) has a factor of \(4\) by checking if the exponent on \(2\) in the prime factorization is even. If so, we can then check if \(X / 4^a \equiv 7\ (\text{mod}\ 8)\) by multiplying all prime factors higher than \(2\), modulo \(8\). Once again, \(X\) can't have more than \(32\) distinct factors as \(N\) and \(K\) are both \(32\)-bit integers, so this computation is also quick.

In the end, if the answer isn't \(1\), \(2\), or \(3\), then it must be \(4\).