Numbers

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

1. Set total = 0.
2. For each base $b$ from $2$ to $A-1$:
   • Run the remainder-guzzling loop described above on $n = A$.
3. You now have numerator $S = \text{total}$ and denominator $D = A-2$.
4. Divide both by $g = \gcd(S,D)$ so the fraction isn't ugly.
5. 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)$.