A number n can be expressed as the sum of k terms where each term's decimal digits are exclusively 1, 2, or 3. The goal is to find the smallest possible k such a decomposition exists. For T ≤ 1000 test cases and n up to 10^18.

Define a function valid(x, m) that returns true if x can be decomposed into m terms satisfying the digit condition. A few observations simplify the search:

• If x < m, it's impossible.
• If m ≤ x ≤ 3m, it's always possible by using terms like 1, 2, or 3.

For larger x, consider the least significant digit. The sum of the least significant digits of all terms modulo 10 must equal x mod 10. Let r = x % 10. Enumerate possible sums i of the least significant digits, where i ranges from r + (r < m ? 10 : 0) to 3m, incremented by 10. For each i, let j be the count of terms contributing to i (i.e., terms with more than one digit). Recursively check if valid((x - i) / 10, j) holds. If any combination works, valid(x, m) is true.

Experimentally, the maximum required k is 5, enabling efficient brute-force checking.

#include <iostream>
using namespace std;
using ll = long long;
bool decomposable(ll value, int termCount) {
    if (value < termCount) return false;
    if (termCount <= value && value <= 3 * termCount) return true;
    int remainder = value % 10;
    int lowerBound = remainder + (remainder < termCount ? 10 : 0);
    for (int sumLSD = lowerBound; sumLSD <= 3 * termCount; sumLSD += 10) {
        for (int multiDigitTerms = 0; multiDigitTerms <= termCount; ++multiDigitTerms) {
            if (decomposable((value - sumLSD) / 10, multiDigitTerms)) return true;
        }
    }
    return false;
}
void processTestCase() {
    ll n; cin >> n;
    int answer = 1;
    while (!decomposable(n, answer)) ++answer;
    cout << answer << '\n';
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while (T--) processTestCase();
    return 0;
}

Splitting Arrays into Monotonic Sequences

Given an array a of length n, construct two sequences b and c such that:

• For all i, a_i = b_i + c_i.
• Sequence b is non-decreasing.
• Sequence c is non-increasing. Minimize the sum of absolute values Σ(|b_i| + |c_i|).

A greedy approach yields optimal assignments: If a_i > a_{i+1}, set b_{i+1} = b_i and c_{i+1} = c_i + a_{i+1} - a_i. Otherwise, set c_{i+1} = c_i and b_{i+1} = b_i + a_{i+1} - a_i.

Let b_1 = x, then c_1 = a_1 - x. Propagate using the rules expresses all b_i and c_i as affine functions of x: b_i = x + β_i, c_i = γ_i - x. The objective becomes Σ|x + β_i| + |γ_i - x|, which is a sum of absolute deviations. The optimal x is the median of the multiset containing all -β_i and γ_i.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    int n; cin >> n;
    vector<ll> a(n);
    for (auto &elem : a) cin >> elem;
    vector<ll> coefficients;
    ll b = a[0], c = 0;
    coefficients.push_back(b);
    coefficients.push_back(c);
    for (int idx = 0; idx < n - 1; ++idx) {
        ll delta = a[idx + 1] - a[idx];
        if (delta >= 0) b += delta;
        else c -= delta;
        coefficients.push_back(b);
        coefficients.push_back(c);
    }
    sort(coefficients.begin(), coefficients.end());
    ll median = coefficients[n]; // There are 2n elements, median at index n (0-indexed)
    ll totalCost = 0;
    for (auto val : coefficients) totalCost += abs(val - median);
    cout << totalCost << '\n';
    return 0;
}

Counting Index Equalities with Floor Functions

Compute the count of integers i from 1 to n such that: A_X + ⌊i / B_X⌋ = A_Y + ⌊i / B_Y⌋. Assume without loss of generality that B_X ≤ B_Y. Define functions f(i) = A_X + i / B_X and g(i) = A_Y + i / B_Y, and their floors F(i) and G(i). The equality F(i) = G(i) holds if and only if the difference h(i) = f(i) - g(i) lies in (-1, 1). Analyze two sub-intervals:

1. h(i) ∈ (-1, 0] implies F(i) - G(i) ∈ {-1, 0}.
2. h(i) ∈ (0, 1) implies F(i) - G(i) ∈ {0, 1}. Focus on the first case. Use binary search to find intervals [l1, r1] where h(i) ∈ (-1, 0] and [l2, r2] where h(i) ∈ (0, 1). The total count equals the number of indices where F(i) = G(i), which can be derived by summing F(i) - G(i) over these intervals and adjusting.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll floorSum(ll a, ll b, ll c, ll n) {
    if (n < 0) return 0;
    if (a == 0 || n == 0) return (n + 1) * (b / c);
    ll total = 0;
    if (a >= c || b >= c) {
        total = n * (n + 1) / 2 * (a / c) + (n + 1) * (b / c);
        a %= c; b %= c;
    }
    ll m = (a * n + b) / c;
    return total + m * n - floorSum(c, c - b - 1, a, m - 1);
}
ll rangeSum(ll a, ll b, ll c, ll l, ll r) {
    return floorSum(a, b, c, r) - floorSum(a, b, c, l - 1);
}
void solve() {
    ll n, ax, bx, ay, by;
    cin >> n >> ax >> bx >> ay >> by;
    if (bx > by) { swap(ax, ay); swap(bx, by); }
    if (bx == by) {
        cout << (ax == ay ? n : 0) << '\n';
        return;
    }
    auto findBoundary = [&](ll targetDiff) -> ll {
        ll low = 1, high = n, result = n + 1;
        while (low <= high) {
            ll mid = (low + high) / 2;
            if (mid * (by - bx) > bx * by * targetDiff) {
                result = mid;
                high = mid - 1;
            } else low = mid + 1;
        }
        return result;
    };
    ll L1 = findBoundary(ay - ax - 1);
    ll L2 = findBoundary(ay - ax);
    ll L3 = n + 1;
    ll low = L2, high = n;
    while (low <= high) {
        ll mid = (low + high) / 2;
        if (mid * (by - bx) <= bx * by * (ay - ax + 1)) {
            L3 = mid;
            low = mid + 1;
        } else high = mid - 1;
    }
    if (L1 > n) { cout << 0 << '\n'; return; }
    L2 = min(L2, n + 1); L3 = min(L3, n);
    ll answer = 0;
    if (L1 < L2) {
        ll diff = rangeSum(1, ay * by, by, L1, L2 - 1) - rangeSum(1, ax * bx, bx, L1, L2 - 1);
        answer += (L2 - L1) - diff;
    }
    if (L2 <= L3) {
        ll diff = rangeSum(1, ax * bx, bx, L2, L3) - rangeSum(1, ay * by, by, L2, L3);
        answer += (L3 - L2 + 1) - diff;
    }
    cout << answer << '\n';
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}

Generating Sequences via Stern-Brocot Tree

Starting from a pair (a, b), repeatedly apply an operation that expands a sequence by inserting sums of adjacnet elements. After n iterations, remove elements exceeding n. Given L and R, output the resulting subsequence.

Represent numbers as linear combinations a·x + b·y. The expansion corresponds to traversing the Stern-Brocot tree. To query a range [L, R], first locate the L-th element via a guided DFS, then enumerate up to R. Use a counting function count(a, b) for the number of valid nodes (with gcd(x,y)=1 and value ≤ n) in the subtree.

count(a, b) = Σ_{d=1}^{n} μ(d) Σ_{i=1}^{⌊n/(d a)⌋} ⌊(⌊n/d⌋ - a i) / b⌋. Compute via a sieve for μ and a floor sum algorithm (e.g., Euclidean-like). Complexity per count is O(√n log n).

During tree traversal, use binary lifting to skip long chains of same-direction moves, ensuring overall efficiency.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 300010;
int aParam, bParam, limitN;
ll queryL, queryR;
int prime[MAXN], primeCnt, mu[MAXN];
bool composite[MAXN];
void sieveInit() {
    mu[1] = 1;
    for (int i = 2; i <= limitN; ++i) {
        if (!composite[i]) { prime[++primeCnt] = i; mu[i] = -1; }
        for (int j = 1; j <= primeCnt && i * prime[j] <= limitN; ++j) {
            composite[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
            mu[i * prime[j]] = -mu[i];
        }
        mu[i] += mu[i - 1];
    }
}
ll floorSum(ll a, ll b, ll c, ll n) {
    // Standard floor sum implementation
    if (n < 0) return 0;
    if (a == 0 || n == 0) return (n + 1) * (b / c);
    ll total = 0;
    if (a >= c || b >= c) {
        total = n * (n + 1) / 2 * (a / c) + (n + 1) * (b / c);
        a %= c; b %= c;
    }
    ll m = (a * n + b) / c;
    return total + m * n - floorSum(c, c - b - 1, a, m - 1);
}
ll countValid(ll coeffA, ll coeffB) {
    ll result = 0;
    for (int d = 1, nextD; d <= limitN; d = nextD + 1) {
        nextD = limitN / (limitN / d);
        ll quotient = limitN / d;
        if (quotient < coeffA + coeffB) break;
        ll term = (mu[nextD] - mu[d - 1]) * floorSum(-coeffA, quotient - coeffA, coeffB, quotient / coeffA);
        result += term;
    }
    return result;
}
int outputBuffer[MAXN], outputPos;
using Fraction = pair<ll, ll>;
inline ll evaluate(const Fraction &frac) {
    return (ll)aParam * frac.first + (ll)bParam * frac.second;
}
void appendValue(const Fraction &frac) {
    outputBuffer[++outputPos] = evaluate(frac);
}
void enumerateRange(const Fraction &left, const Fraction &right, ll startIdx, ll endIdx) {
    if (outputPos >= endIdx - startIdx + 1) return;
    ll midVal = evaluate({left.first + right.first, left.second + right.second});
    if (midVal > limitN) return;
    enumerateRange(left, {left.first + right.first, left.second + right.second}, startIdx, endIdx);
    if (outputPos < endIdx - startIdx + 1) appendValue({left.first + right.first, left.second + right.second});
    enumerateRange({left.first + right.first, left.second + right.second}, right, startIdx, endIdx);
}
void locateAndCollect(const Fraction &left, const Fraction &right, ll startIdx, ll endIdx) {
    if (outputPos >= endIdx - startIdx + 1) return;
    ll valLeft = evaluate(left), valRight = evaluate(right);
    ll midVal = evaluate({left.first + right.first, left.second + right.second});
    if (midVal > limitN) return;
    ll subtreeCount = countValid(valLeft, midVal) + 1;
    if (startIdx == subtreeCount) {
        appendValue({left.first + right.first, left.second + right.second});
        enumerateRange({left.first + right.first, left.second + right.second}, right, startIdx, endIdx);
        return;
    }
    if (startIdx < subtreeCount) {
        int step = 0;
        for (int bit = 20; bit >= 0; --bit) {
            int candidate = step + (1 << bit);
            if (startIdx < countValid(valLeft, evaluate({left.first * candidate + right.first, left.second * candidate + right.second})) + 1)
                step = candidate;
        }
        locateAndCollect(left, {left.first * step + right.first, left.second * step + right.second}, startIdx, endIdx);
        for (int k = step; k >= 1; --k) {
            if (outputPos >= endIdx - startIdx + 1) break;
            appendValue({left.first * k + right.first, left.second * k + right.second});
            enumerateRange({left.first * k + right.first, left.second * k + right.second},
                           {left.first * (k - 1) + right.first, left.second * (k - 1) + right.second}, startIdx, endIdx);
        }
    } else {
        ll totalCount = countValid(valLeft, valRight);
        int step = 0;
        for (int bit = 20; bit >= 0; --bit) {
            int candidate = step + (1 << bit);
            if (totalCount - startIdx + 1 < countValid(evaluate({left.first + right.first * candidate, left.second + right.second * candidate}), valRight) + 1)
                step = candidate;
        }
        ll newStart = totalCount - countValid(evaluate({left.first + right.first * step, left.second + right.second * step}), valRight);
        locateAndCollect({left.first + right.first * step, left.second + right.second * step}, right, startIdx - newStart, endIdx - newStart);
    }
}
int main() {
    cin >> aParam >> bParam >> limitN >> queryL >> queryR;
    sieveInit();
    ll totalElements = countValid(aParam, bParam);
    if (queryL != totalElements + 2 && queryR != 1) {
        locateAndCollect({1, 0}, {0, 1}, max(queryL - 1, 1LL), min(queryR - 1, totalElements));
    }
    if (queryL == 1) cout << aParam << ' ';
    for (int idx = 1; idx <= outputPos; ++idx) cout << outputBuffer[idx] << ' ';
    if (queryR == totalElements + 2) cout << bParam << ' ';
    cout << '\n';
    return 0;
}