main.cpp

#include <cstdint>
#include <iostream>
#include <tuple>
#include <utility>

const std::size_t COUNT = 9;
const std::uint8_t primes[COUNT] = {2, 3, 7, 11, 13, 17, 19, 23, 29};

std::pair<int64_t, int64_t> extended_gcd(int a, int b) {
  auto [old_r, r] = std::pair{a, b};
  auto [old_s, s] = std::pair{1, 0};
  auto [old_t, t] = std::pair{0, 1};

  while (r != 0) {
    auto quotient = old_r / r;

    std::tie(old_r, r) = std::pair{r, old_r - quotient * r};
    std::tie(old_s, s) = std::pair{s, old_s - quotient * s};
    std::tie(old_t, t) = std::pair{t, old_t - quotient * t};
  }

  return {old_s, old_t};
}

int64_t combine(int64_t a1, int64_t a2, int64_t n1, int64_t n2) {
  auto [m1, m2] = extended_gcd(n1, n2);

  return (a1 * m2 * n2 + a2 * m1 * n1);
}

struct number {
  std::uint8_t remainders[COUNT];

  number(int n) {
    for (int i = 0; i < COUNT; i++) {
      remainders[i] = n % primes[i];
    }
  }

  number operator+(const number &rhs) const noexcept {
    number result = 0;

    for (int i = 0; i < COUNT; i++) {
      result.remainders[i] = (remainders[i] + rhs.remainders[i]) % primes[i];
    }

    return result;
  }

  number &operator+=(const number &rhs) noexcept {
    for (int i = 0; i < COUNT; i++) {
      remainders[i] = (remainders[i] + rhs.remainders[i]) % primes[i];
    }

    return *this;
  }

  number operator-() const noexcept {
    number result = *this;

    for (int i = 0; i < COUNT; i++) {
      result.remainders[i] = (primes[i] - result.remainders[i]) % primes[i];
    }

    return result;
  }

  number operator-(const number &rhs) const noexcept { return *this + -rhs; }

  number &operator-=(const number &rhs) noexcept {
    *this += -rhs;
    return *this;
  }

  number operator*(const number &rhs) const noexcept {
    number result = 0;

    for (int i = 0; i < COUNT; i++) {
      result.remainders[i] = (remainders[i] * rhs.remainders[i]) % primes[i];
    }

    return result;
  }

  number &operator*=(const number &rhs) noexcept {
    for (int i = 0; i < COUNT; i++) {
      remainders[i] = (remainders[i] * rhs.remainders[i]) % primes[i];
    }

    return *this;
  }

  operator int() const noexcept {
    int64_t a = 0;
    int64_t n = 1;

    for (int i = 0; i < COUNT; i++) {
      a = combine(a, remainders[i], n, primes[i]);
      n *= primes[i];

      a %= n;
      a += n;
      a %= n;
    }

    return a;
  }
};

int main() {
  for (int i = 1'000'000; i < 1'000'001'000; i++) {
    std::cout << i << ": " << (int)number(i) << '\n';
  }
}