AOC_2_2_improved.cpp

// helpers you already have:
// - __int128 pow10_128[k] for k up to max digits (pow10_128[0] = 1)
// - vector<vector<int>> DIV where DIV[L] gives proper divisors of L (or you can compute divisors on the fly)
// - count_digits(n) etc.

// Utility: floor_div, ceil_div for __int128
static inline __int128 floor_div128(__int128 x, __int128 y) {
  return x / y;
}
static inline __int128 ceil_div128(__int128 x, __int128 y) {
  if (y < 0) x = -x, y = -y;
  if (x >= 0) return (x + y - 1) / y;
  return x / y; // negative case (shouldn't happen for our positive args)
}

// sum of integers from L..R as __int128
static inline __int128 sum_range(__int128 L, __int128 R) {
  if (L > R) return 0;
  __int128 cnt = R - L + 1;
  return (L + R) * cnt / 2;
}

// safe lcm with overflow guard: if lcm > limit, return limit+1 (means "too large")
__int128 safe_lcm(__int128 a, __int128 b, __int128 limit) {
  if (a == 0 || b == 0) return 0;
  __int128 g = std::gcd((long long)a, (long long)b); // careful: gcd for __int128; we'll implement general gcd
  // implement gcd for __int128:
  auto gcd128 = [&](auto self, __int128 x, __int128 y) -> __int128 {
    while (y != 0) { __int128 r = x % y; x = y; y = r; }
    return x >= 0 ? x : -x;
  };
  g = gcd128(gcd128, a, b);
  __int128 na = a / g;
  // check overflow: if na > limit / b, then lcm > limit
  if (na != 0 && b > limit / na) return limit + 1;
  return na * b;
}

// better: an inline gcd128 function
static inline __int128 gcd128(__int128 a, __int128 b) {
  if (a < 0) a = -a;
  if (b < 0) b = -b;
  while (b != 0) {
    __int128 r = a % b;
    a = b;
    b = r;
  }
  return a;
}
static inline __int128 lcm_capped(__int128 a, __int128 b, __int128 cap) {
  if (a == 0 || b == 0) return 0;
  __int128 g = gcd128(a, b);
  __int128 na = a / g;
  if (na > 0 && b > cap / na) return cap + 1;
  return na * b;
}

__int128 sum_repeated_numbers_between(__int128 a, __int128 b, const vector<__int128>& pow10) {
  if (a > b) return 0;
  int digits_a = 0, digits_b = 0;
  { __int128 tmp = a; while (tmp) { ++digits_a; tmp /= 10; } if (a == 0) digits_a = 1; }
  { __int128 tmp = b; while (tmp) { ++digits_b; tmp /= 10; } if (b == 0) digits_b = 1; }

  int maxDigits = (int)pow10.size() - 1;
  __int128 final_ans = 0;
  int global_max_digits = digits_b;

  // p = minimal block length
  for (int p = 1; p <= global_max_digits / 2; ++p) {
    // list proper divisors of p
    vector<int> proper_divs;
    for (int d = 1; d * 1ll * d <= p; ++d) {
      if (p % d == 0) {
        if (d < p && d != p) proper_divs.push_back(d);
        int other = p / d;
        if (other != d && other < p) proper_divs.push_back(other);
      }
    }
    sort(proper_divs.begin(), proper_divs.end());

    // t is times repeated, t >= 2
    for (int t = 2; p * t <= global_max_digits; ++t) {
      int L = p * t; // total digits
      // R = (10^L - 1) / (10^p - 1)
      __int128 tenL = pow10[L];
      __int128 tenP = pow10[p];
      __int128 R = (tenL - 1) / (tenP - 1);

      // clamp loN, hiN to digit range L
      __int128 loN = a;
      __int128 hiN = b;
      __int128 minL = pow10[L - 1];
      __int128 maxL = pow10[L] - 1;
      if (loN < minL) loN = minL;
      if (hiN > maxL) hiN = maxL;
      if (loN > hiN) continue;

      // allowable x range (block value must be p-digit number)
      __int128 x_min = ceil_div128(loN, R);
      __int128 x_max = floor_div128(hiN, R);
      __int128 x_lo = x_min;
      __int128 x_hi = x_max;
      __int128 minX = pow10[p - 1];
      __int128 maxX = pow10[p] - 1;
      if (x_lo < minX) x_lo = minX;
      if (x_hi > maxX) x_hi = maxX;
      if (x_lo > x_hi) continue;

      // sum of all x in [x_lo, x_hi]
      __int128 sum_all_x = sum_range(x_lo, x_hi);

      // we need to subtract x that have smaller period (i.e., repeats of some d|p, d < p)
      // Each divisor d gives Srep = (10^p - 1)/(10^d - 1). Such x are multiples of Srep.
      // We do inclusion-exclusion over proper_divs.

      int m = (int)proper_divs.size();
      __int128 subtract_sum = 0;
      // iterate non-empty subsets
      int subsets = 1 << m;
      __int128 cap = maxX; // if lcm > maxX then no multiples
      for (int mask = 1; mask < subsets; ++mask) {
        // compute lcm of Srep for divisors in subset
        __int128 l = 1;
        bool overflowed = false;
        int bits = __builtin_popcount((unsigned)mask);
        for (int i = 0; i < m; ++i) if (mask & (1 << i)) {
          int d = proper_divs[i];
          // Srep = (10^p - 1) / (10^d - 1)
          __int128 Srep = (pow10[p] - 1) / (pow10[d] - 1);
          // l = lcm(l, Srep) but capped
          __int128 nl = lcm_capped(l, Srep, cap);
          if (nl > cap) { overflowed = true; break; }
          l = nl;
        }
        if (overflowed || l == 0) continue;
        // multiples of l in [x_lo, x_hi]
        __int128 ylow = ceil_div128(x_lo, l);
        __int128 yhigh = floor_div128(x_hi, l);
        if (ylow > yhigh) continue;
        __int128 sum_mult = sum_range(ylow, yhigh) * l; // sum of multiples
        if (bits % 2 == 1) subtract_sum += sum_mult; // odd subset size => subtract
        else subtract_sum -= sum_mult; // even subset size => add back
      }

      __int128 primitive_sum_x = sum_all_x - subtract_sum;
      if (primitive_sum_x > 0) {
        final_ans += primitive_sum_x * R;
      }
    } // end t
  } // end p

  return final_ans;
}