10CUnreviewed2000Kimi K2.6 (thinking)

Digital Root

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

number theory

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.

Stop and think: what is $d(x)$ in terms of $x \bmod 9$ ? For two positive numbers, when does $d(x) = d(y)$ ?

Use that to rewrite Billy's check. Show that $d(d(A)d(B)) = d(C)$ is the same thing as $AB \equiv C \pmod{9}$ . So a 'mistake' is a triple where $AB \neq C$ yet $AB \equiv C \pmod{9}$ .

Fix a pair $(A,B)$ . How many $C \in [1,N]$ satisfy $C \equiv AB \pmod{9}$ ? It depends only on the residue of $AB$ . What if you precomputed, for each residue $r$ , how many numbers in $[1,N]$ are $\equiv r \pmod{9}$ ?

Since $AB \bmod 9$ is determined by $A \bmod 9$ and $B \bmod 9$ , you can group all three variables by residue. If $\text{freq}[r]$ is that count, the total number of triples passing Billy's test is $\sum_{i=0}^8 \sum_{j=0}^8 \text{freq}[i] \cdot \text{freq}[j] \cdot \text{freq}[(ij) \bmod 9]$ .

The only triples counted above that are not mistakes are those with $AB = C$ . Count those by summing $\lfloor N/A \rfloor$ for $A=1$ to $N$ . Subtract that sum from the double-sum above. That's your answer, computed in $O(N)$ .

Observation 1: Digital Root is Just Mod 9 With Extra Steps

For $x \ge 1$ , the digital root $d(x)$ is exactly $x \bmod 9$ , except when the remainder is $0$ you write $9$ instead. Therefore $d(x) = d(y) \iff x \equiv y \pmod{9}.$

Observation 2: Billy's Test is a Congruence

Since $d(A) \equiv A \pmod{9}$ and $d(B) \equiv B \pmod{9}$ , Billy's check $d(d(A)d(B)) = d(C)$ collapses to $AB \equiv C \pmod{9}.$ This is necessary for $AB = C$ , but not sufficient. We need ordered triples $(A,B,C)$ with $1 \le A,B,C \le N$ such that the congruence holds but $AB \neq C$ .

Observation 3: Count the Congruent Triples

Only residues modulo $9$ matter. Define $\text{freq}[r] = \bigl|\{ x \in [1,N] : x \bmod 9 = r \}\bigr|, \qquad r = 0,\dots,8.$ If $A \equiv i$ and $B \equiv j \pmod{9}$ , then $AB \equiv ij \pmod{9}$ . For this pair there are exactly $\text{freq}[(ij) \bmod 9]$ choices of $C$ satisfying the congruence. Grouping all pairs by residue gives $S_{\text{cong}} = \sum_{i=0}^{8} \sum_{j=0}^{8} \text{freq}[i] \cdot \text{freq}[j] \cdot \text{freq}[(ij) \bmod 9].$ That is a puny $9^3 = 729$ iterations.

Observation 4: Subtract the Exact Matches

Among those triples, the ones with $AB = C$ are not mistakes. For a fixed $A$ , the admissible $B$ are those with $AB \le N$ ; there are $\lfloor N/A \rfloor$ of them, and $C$ is forced to be $AB$ . Hence $S_{\text{eq}} = \sum_{A=1}^{N} \Bigl\lfloor \frac{N}{A} \Bigr\rfloor.$ For $N \le 10^6$ a plain $O(N)$ loop is more than fast enough.

Final Answer

$\boxed{\text{answer} = S_{\text{cong}} - S_{\text{eq}}}$

Complexity: $O(N)$ time and $O(1)$ additional memory.

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

using ll = long long;

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

int main() {
    setIO();
    ll n;
    if (!(cin >> n)) return 0;

    array<ll, 9> freq{};
    for (int r = 0; r < 9; ++r) {
        if (r == 0) {
            freq[r] = n / 9;
        } else {
            freq[r] = n / 9 + (n % 9 >= r ? 1 : 0);
        }
    }

    ll congruent = 0;
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            int k = (i * j) % 9;
            congruent += freq[i] * freq[j] * freq[k];
        }
    }

    ll exact = 0;
    for (ll a = 1; a <= n; ++a) {
        exact += n / a;
    }

    cout << congruent - exact << '\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();
    ll n;
    if (!(cin >> n)) return 0;

    array<ll, 9> freq{};
    for (int r = 0; r < 9; ++r) {
        if (r == 0) {
            freq[r] = n / 9;
        } else {
            freq[r] = n / 9 + (n % 9 >= r ? 1 : 0);
        }
    }

    ll congruent = 0;
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j) {
            int k = (i * j) % 9;
            congruent += freq[i] * freq[j] * freq[k];
        }
    }

    ll exact = 0;
    for (ll a = 1; a <= n; ++a) {
        exact += n / a;
    }

    cout << congruent - exact << '\n';
    return 0;
}

View on Codeforces Back to the list