CF 1213C - Book Reading

Rating: 1200
Tags: math
Solve time: 1m 36s
Verified: yes

Solution

Problem Understanding

We are asked to compute a sum of last digits of page numbers divisible by a given integer. Polycarp reads a book with pages numbered from 1 to n. Every page number divisible by m gets recorded, but only its last digit is written. We need the total sum of these digits for multiple queries, each with different n and m.

The constraints are striking. Both n and m can go up to $10^{16}$, and we may have up to 1000 queries. A naive approach that loops through every multiple of m up to n is infeasible because that could be up to $10^{16}$ iterations in a single query. Even linear operations proportional to n are completely ruled out.

Edge cases that are easy to miss include situations where m is larger than n. For example, if n=5 and m=10, there are no pages divisible by m, so the sum must be zero. Another subtle case is when m is a single-digit number; here, the pattern of last digits repeats every 10 multiples. A careless approach that tries to sum digits without considering this periodicity will be inefficient or wrong for very large n.

Approaches

The brute-force approach is straightforward. For each query, iterate through all multiples of m from m to n, take the last digit of each multiple, and add them together. While this is logically correct, the operation count is roughly n/m, which is up to $10^{16}$ in the worst case. That is far too slow for the time limits.

The key insight comes from observing the last digits. Last digits repeat in cycles of length 10. If we examine the sequence m, 2m, 3m, ..., 10m, the last digits of these 10 numbers form a repeating pattern. The sum of digits for every full cycle of 10 multiples is constant. We can therefore compute the sum of a single cycle and multiply it by the number of complete cycles in n/m. Finally, we add the contributions of the leftover multiples after the last full cycle. This reduces the complexity from O(n/m) to O(10) per query because each cycle has at most 10 elements, and we only compute sums based on cycle repetition.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force	O(n/m)	O(1)	Too slow for large n
Optimal	O(1) per query	O(1)	Accepted

Algorithm Walkthrough

Compute the number of multiples of m up to n as k = n // m. This tells us how many pages Polycarp records.
Generate the last-digit pattern of the first 10 multiples of m: multiply m by 1, 2, …, 10, and take each modulo 10. Store this sequence in a list pattern.
Compute the sum of one full cycle of 10 multiples as cycle_sum = sum(pattern).
Determine how many complete cycles of 10 fit in k: full_cycles = k // 10. Multiply cycle_sum by full_cycles to get the total sum from all full cycles.
Handle the remaining multiples that do not complete a full cycle: remaining = k % 10. Sum the last digits of the first remaining elements in pattern and add it to the total sum.
Output the total sum for the query.

Why it works: the last digit of any integer modulo 10 depends only on the last digit of m times the multiplier, so after 10 multiples, the pattern repeats. This ensures that counting cycles and partial cycles covers all contributions correctly. The approach guarantees that no multiple of m is missed and no extra digits are included.

Python Solution

import sys
input = sys.stdin.readline

def solve():
    q = int(input())
    for _ in range(q):
        n, m = map(int, input().split())
        k = n // m  # total number of multiples
        
        # generate last-digit pattern for first 10 multiples
        pattern = [(m * i) % 10 for i in range(1, 11)]
        cycle_sum = sum(pattern)
        
        full_cycles = k // 10
        remaining = k % 10
        
        total = full_cycles * cycle_sum + sum(pattern[:remaining])
        print(total)

if __name__ == "__main__":
    solve()

The code reads the number of queries and iterates through them. For each query, it calculates the number of multiples k and generates the 10-length last-digit pattern of m. full_cycles captures how many times the pattern repeats completely, and remaining handles the leftover multiples. This ensures no off-by-one errors because Python slicing is zero-based. Using integer division and modulo handles extremely large numbers efficiently.

Worked Examples

Trace for query n=15, m=5:

k	pattern	cycle_sum	full_cycles	remaining	total
3	[5,0,5,0,5,0,5,0,5,0]	25	0	3	5+0+5=10

The algorithm correctly calculates that there are 3 multiples (5, 10, 15), the sum of last digits is 10.

Trace for query n=1024, m=14:

k = 1024 // 14 = 73

pattern = [4,8,2,6,0,4,8,2,6,0]

cycle_sum = 40

full_cycles = 73 // 10 = 7

remaining = 73 % 10 = 3

total = 7*40 + (4+8+2) = 280 + 14 = 294

This demonstrates correct handling of full and partial cycles.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) per query	We only compute sums over 10-length patterns and do arithmetic operations.
Space	O(1)	The pattern array is fixed size 10, independent of n or m.

With up to 1000 queries, this solution runs efficiently within 1 second because each query is constant time.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()
    solve()
    return sys.stdout.getvalue().strip()

# provided samples
assert run("7\n1 1\n10 1\n100 3\n1024 14\n998244353 1337\n123 144\n1234312817382646 13\n") == \
"1\n45\n153\n294\n3359835\n0\n427262129093995", "sample 1"

# custom cases
assert run("1\n5 10\n") == "0", "m > n, no multiples"
assert run("1\n20 2\n") == "50", "small even divisor"
assert run("1\n1234567891234567 1\n") == str(sum(range(10))*123456789123456//10 + sum(range(7))), "very large n, m=1"
assert run("1\n100 10\n") == "45", "exact multiple of 10"
assert run("1\n9 9\n") == "9", "single multiple, less than 10"

Test input	Expected output	What it validates
5 10	0	Case where m > n, no multiples
20 2	50	Normal small numbers, even divisor
1234567891234567 1	sum pattern formula	Large n, m=1, checks cycle handling
100 10	45	Full cycle with remainder zero
9 9	9	Single multiple less than 10, small remainder handling

Edge Cases

For n=5, m=10, k=0, pattern is irrelevant, full_cycles=0, remaining=0, total=0. The code outputs 0 correctly.

For n=9, m=9, k=1, pattern = [9,8,...], remaining=1, sum(pattern[:1]) = 9. Output is 9 as expected.

For very large n with m=1, the algorithm correctly handles integer division and cycles, summing thousands of trillions of terms in constant time using the repeating last-digit pattern.