2022/finals/emerald_exhibiting.cpp

#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;
}