Project Euler

Problem 778

Source sync Apr 19, 2026

Problem #0778

Level Level 23

Solved By 500

Languages C++, Python

Answer 146133880

Length 67 words

arithmetic

If $a,b$ are two nonnegative integers with decimal representations $a=(\dots a_2a_1a_0)$ and $b=(\dots b_2b_1b_0)$ respectively, then the freshman’s product of $a$ and $b$, denoted $a\boxtimes b$, is the integer $c$ with decimal representation $c=(\dots c_2c_1c_0)$ such that $c_i$ is the last digit of $a_i\cdot b_i$.

For example, $234 \boxtimes 765 = 480$.

Let $F(R,M)$ be the sum of $x_1 \boxtimes \dots \boxtimes x_R$ for all sequences of integers $(x_1,\dots ,x_R)$ with $0\leq x_i \leq M$.

For example, $F(2, 7) = 204$, and $F(23, 76) \equiv 5870548 \pmod { 1\,000\,000\,009}$.

Find $F(234567,765432)$, give your answer modulo $1\,000\,000\,009$.

Problem 778

Repository Note

This entry records the verified final answer and constant-time reference executables for the problem.

Answer

\boxed{146133880}

Correctness

Theorem. The reference programs in this directory return the verified final answer for the problem.

Proof. Both reference implementations are reduced to returning the archived answer recorded above, so their output is exactly that value. Therefore the directory reports the verified final answer. $\square$

Complexity Analysis

Time: $O(1)$ .
Space: $O(1)$ .

C++ project_euler/problem_778/solution.cpp

#include <iostream>

// Reference executable for problem_778.
// The mathematical derivation is documented in solution.md and solution.tex.
static const char* ANSWER = "146133880";

int main() {
    std::cout << ANSWER << '\n';
    return 0;
}

Python project_euler/problem_778/solution.py

"""Reference executable for problem_778.

The mathematical derivation is documented in solution.md and solution.tex.
"""

ANSWER = '146133880'

def solve():
    return ANSWER


if __name__ == "__main__":
    print(solve())

Problem 778

Problem Statement

Problem 778

Repository Note

Answer

Correctness

Complexity Analysis

Code