Problem: emerald_exhibiting (2022 finals)

Ishiko is opening a bracelet shop. Each bracelet she plans to sell is expressed as a ring of \(N\) colored beads, with exactly \(K\) green beads made of emerald, and \(N-K\) remaining beads of all unique colors (neither green nor the same as any other bead in the bracelet). Ishiko has an infinite number of beads available for each of these \(N - K + 1\) different colors.

Ishiko wants to exhibit *one copy of every possible distinct bracelet*. Two bracelets are considered distinct if one is not a cyclic rotation of the other. For instance, the two bracelets on the left are distinct, but the two bracelets on the right are not:

{{PHOTO_ID:876374553707415|WIDTH:700}}

A vendor takes orders for triangular display cases of arbitrary positive integer heights. A case of height \(H\) has \(H\) rows, where the \(i\)th row has \(2*i - 1\) slots, each slot capable of holding one bracelet. For example, a case of height \(3\) is shown below and holds \(1 + 3 + 5 = 9\) bracelets:

{{PHOTO_ID:547949757342773|WIDTH:700}}

How many display cases (of possibly differing heights) will Ishiko need to buy to exhibit one copy of every possible bracelet *without leaving any empty slots in the display cases*?


# Constraints

\(1 \le T \le 110\)
\(1 \le N \le 10^9\)
\(0 \le K \le N\)

The sum of \(N\) across all test cases is at most \(8{,}000{,}000{,}000\).


# Input Format

Input begins with an integer \(T\), the number of cases. For each case, there is a line containing two space-separated integers, \(N\) and \(K\).


# Output Format

For the \(i\)th case, print `"Case #i: "` followed by a single integer, the minimum number of display cases that Ishiko needs to purchase to exhibit one copy of each bracelet.


# Sample Explanation

In the first sample case, let's say that Ishiko's beads are green, blue, and red. There are \(4\) possible bracelets for \(N = 5\) beads with \(K = 3\) green beads, \(1\) red bead, and \(1\) blue bead (up to rotation):

{{PHOTO_ID:1327255974690671|WIDTH:700}}

Ishiko can use a single display case of height \(2\) to display these \(4\) bracelets.

In the second sample case, let's say that Ishiko's beads are green, blue, red, and yellow. There are \(20\) possible bracelets for \(N = 6\) beads with \(K = 3\) green beads, \(1\) blue bead, \(1\) red bead, and \(1\) yellow bead. Some examples are:

{{PHOTO_ID:853886435922998|WIDTH:700}}

Ishiko can display these bracelets if she purchases a case of height \(2\) and a case of height \(4\).

In the third sample case, there are \(60\) possible bracelets and Ishiko needs at least \(4\) display cases to display all of them. One possibility is that she buys two cases of height \(1\), one case of height \(3\), and one case of height \(7\).


Sample input:
4
5 3
6 3
6 2
243447 42273


Sample output:
Case #1: 1
Case #2: 2
Case #3: 4
Case #4: 4


Solution: 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\).







Code: #include <bitset>
#include <cmath>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

const int LIM = (int)1e9 + 1;
const bool READ_PRIMES_FROM_FILE = true;

vector<int> primes;

void load_primes() {
  primes.reserve(51000000);
  if (READ_PRIMES_FROM_FILE) {
    ifstream fin("primes.txt");
    for (int p; fin >> p;) {
      primes.push_back(p);
    }
  } else {
    bitset<LIM> sieve;
    int lim = sqrt(LIM);
    for (int i = 3; i < lim; i += 2) {
      if (!sieve[i] && i % 2 == 1) {
        for (int j = i * 2; j < LIM; j += i) {
          sieve.set(j);
        }
      }
    }
    primes.push_back(2);
    for (int i = 3; i <= LIM; i += 2) {
      if (!sieve[i]) {
        primes.push_back(i);
      }
    }
  }
}

// Returns k in the p^k term of the prime factorization of N!.
int legendre_exp(int p, int N) {
  int ans = 0;
  for (long long base = p; base <= N; base *= p) {
    ans += N / base;
  }
  return ans;
}

int powmod8(int p, int exp) {
  int ans = 1;
  for (exp %= 8; exp > 0; exp--) {
    ans = (ans * p) % 8;
  }
  return ans;
}

int N, K;

int solve() {
  bool is_one = true, is_two = true, two_exp_even = false;
  int mod8prod = 1;
  for (int p : primes) {
    if (p > N) {
      break;
    }
    int exp = legendre_exp(p, N) - legendre_exp(p, K);
    if (exp % 2 != 0) {
      is_one = false;
    }
    if (p % 4 == 3 && exp % 2 == 1) {
      is_two = false;
    }
    if (p == 2 && exp % 2 == 0) {
      two_exp_even = true;
    }
    if (p > 2) {
      mod8prod = (mod8prod * powmod8(p, exp)) % 8;
    }
  }
  bool is_three = !(two_exp_even && mod8prod == 7);
  return is_one ? 1 : is_two ? 2 : is_three ? 3 : 4;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  load_primes();
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cin >> N >> K;
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}