13AUnreviewed1000Kimi K2.6 (thinking)

Numbers

Progressive hints first, then the full explanation and implementation when you're ready to cash out.

implementation math

Original problem

Review status

AI-generated and still unreviewed. Double-check the details before internalizing them.

Hints

Progressive nudges

Open only as much as you need to keep the solve alive.

An average has two ingredients: a total sum and a count. How many bases are you averaging over?

Do you remember how to pull out the digits of a number when you write it in base $b$ ? Think about remainders and division.

$A \le 1000$ , which means there are fewer than $1000$ bases to check. Simulating the conversion for each base is more than fast enough.

The answer must be an irreducible fraction. Once you have the total sum of all digit-sums, what arithmetic operation do you need to perform on both the numerator and the denominator before printing?

Loop $b$ from $2$ to $A-1$ . For each base, start with $n = A$ and repeatedly add $n \bmod b$ to your answer while replacing $n$ with $\lfloor n / b \rfloor$ . Your final fraction is $\frac{\text{answer}}{A-2}$ , simplified by their greatest common divisor.

Observation

Petya wants the average digit sum across bases $2, 3, \dots, A-1$ . An average is just sum divided by count. The count of bases is $A-2$ . That's the easy part.

Digit Sum in Any Base

Converting to base $b$ is kindergarten stuff: while your number is still breathing, grab the last digit with $n \bmod b$ , add it to your running total, then kill it with $n \leftarrow \lfloor n/b \rfloor$ . Repeat until it's zero.

Algorithm

Set total = 0.
For each base $b$ $b$ from $2$ $2$ to $A-1$ $A - 1$ :
- Run the remainder-guzzling loop described above on $n = A$ .
You now have numerator $S = \text{total}$ and denominator $D = A-2$ .
Divide both by $g = \gcd(S,D)$ so the fraction isn't ugly.
Print $S/g$ and $D/g$ separated by a slash.

Why It Works (a.k.a. Proof)

Lemma 1: For a fixed base $b$ , the inner loop computes the exact digit sum of $A$ in base $b$ . Proof: Each iteration peels off the current least significant digit ( $n \bmod b$ ) and shifts the number right one digit ( $n /= b$ ). The accumulator adds every digit exactly once. $\square$

Lemma 2: After processing all bases, total equals $\sum_{b=2}^{A-1} S_b$ , where $S_b$ is the digit sum in base $b$ . Proof: By Lemma 1, each outer-loop iteration contributes exactly $S_b$ , and we visit every base in $[2,A-1]$ . $\square$

Theorem: The algorithm outputs the required average as an irreducible fraction. Proof: From Lemma 2, the numerator is the correct total. The denominator is $A-2$ , the exact number of terms. Dividing by $\gcd$ removes any common factors, giving the unique reduced form. $\square$

Complexity Analysis

$A \le 1000$ . The outer loop runs $O(A)$ times; the inner loop needs $O(\log_b A)$ steps per base. Total time is $\sum_{b=2}^{A-1} O(\log_b A) = O(A \log A),$ which for these constraints is basically a rounding error. Memory is $O(1)$ .

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();
    
    int A;
    if (!(cin >> A)) return 0;
    
    ll total = 0;
    for (int b = 2; b <= A - 1; ++b) {
        int n = A;
        while (n > 0) {
            total += n % b;
            n /= b;
        }
    }
    
    ll denom = A - 2;
    ll g = gcd(total, denom);
    cout << total / g << '/' << denom / g << '\n';
    
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

int main() {
    setIO();
    
    int A;
    if (!(cin >> A)) return 0;
    
    ll total = 0;
    for (int b = 2; b <= A - 1; ++b) {
        int n = A;
        while (n > 0) {
            total += n % b;
            n /= b;
        }
    }
    
    ll denom = A - 2;
    ll g = gcd(total, denom);
    cout << total / g << '/' << denom / g << '\n';
    
    return 0;
}

View on Codeforces Back to the list