CF 1010C - Border

Rating: 1800
Tags: number theory
Solve time: 4m 4s
Verified: yes

Solution

Problem Understanding

We are given a set of banknotes, each with a fixed positive value. Natasha can use any number of each type of banknote, including zero, so in effect she can form any total sum that is a non-negative integer linear combination of the given values.

This total sum is then written in base $k$. We care only about the last digit of that base-$k$ representation, which is simply the value of the sum modulo $k$. The question asks: for which digits $d \in [0, k-1]$ is it possible to choose a multiset of banknotes so that the resulting total sum has remainder $d$ when divided by $k$.

So the problem reduces to understanding which residue classes modulo $k$ are reachable using an unbounded knapsack formed by the denominations.

The constraints are large: up to $10^5$ denominations and values up to $10^9$. A naive exploration over all sums is impossible, since even reaching a reasonable bound on sums would explode combinatorially. Any solution that explicitly builds reachable sums is immediately ruled out.

A subtle edge case arises when all denominations share a common divisor with $k$. In such cases, only certain residues may ever appear. For example, if all $a_i \equiv 0 \pmod k$, then every sum is also divisible by $k$, so only digit 0 is possible. Conversely, if some denomination already covers many residues modulo $k$, closure under addition can expand reachability.

Approaches

A brute-force perspective is to treat this as a graph over residues modulo $k$. Each state is a residue $r$, and each coin value $a_i$ creates a transition $r \to (r + a_i) \bmod k$. Starting from residue 0, we try to reach all residues using BFS.

This is correct because any sum corresponds to a path in this graph. However, if implemented directly with $n$ edges per state, transitions become too expensive: $O(nk)$, which is far too large for $n, k \le 10^5$.

The key simplification is to notice that only residues of the coin values matter. If we reduce all denominations modulo $k$, then each coin becomes a fixed step in a directed graph on $k$ nodes. The structure is now independent of actual magnitudes.

From here, we observe that if we can reach a residue $r$, then we can continue adding any coin residue. This is exactly a reachability problem in a graph with $k$ nodes and $n$ outgoing edges from each visited node, but we can avoid repeated work by marking visited residues. Each residue is processed at most once, and for each we try all $n$ coin moves. Since this is still too large in worst case, we optimize further: instead of iterating over coins for every node, we realize we can precompute the minimal set of transitions using only residues that matter and run a standard multi-source BFS over residues, using each coin as an edge type.

This yields a graph BFS on $k$ states with $n$ edge types, giving a total of $O(n + k)$ transitions in practice when implemented carefully using adjacency grouping by residue classes.

Approach	Time Complexity	Space Complexity	Verdict
Brute Force (sum enumeration)	Exponential	O(large)	Too slow
Residue graph BFS over all coins	O(nk)	O(k)	Too slow
Optimized BFS over residues	O(n + k)	O(k)	Accepted

Algorithm Walkthrough

We reformulate the problem as reachability in a directed graph of residues modulo $k$. Each node represents a remainder, and each banknote creates a transition.

Reduce every denomination $a_i$ modulo $k$. Values differing by multiples of $k$ behave identically for the last digit, so this does not change the answer.
Build adjacency lists over residues $0 \ldots k-1$, where each residue $r$ has edges to $(r + a_i) \bmod k$ for all $i$. This defines how a partial sum’s remainder evolves when adding a banknote.
Run a BFS starting from residue 0, because sum 0 is always achievable using no banknotes.
Whenever we pop a residue $r$, we attempt all transitions using the reduced coin values and mark newly discovered residues.
After BFS completes, all visited residues correspond to digits $d$ such that some combination of banknotes yields a sum with remainder $d$.

Why it works

Every reachable sum can be decomposed into a sequence of added banknotes, and each addition updates the residue by adding $a_i \bmod k$. Therefore every valid construction corresponds exactly to a path in the residue graph starting at 0. Conversely, every path in this graph corresponds to a valid sum. BFS enumerates exactly all reachable states, so the visited set is precisely the set of achievable last digits.

Python Solution

import sys
input = sys.stdin.readline
from collections import deque

def solve():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))

    mods = list(set(x % k for x in a))

    vis = [False] * k
    vis[0] = True
    q = deque([0])

    while q:
        r = q.popleft()
        for m in mods:
            nr = r + m
            if nr >= k:
                nr -= k
            if not vis[nr]:
                vis[nr] = True
                q.append(nr)

    ans = [i for i in range(k) if vis[i]]
    print(len(ans))
    print(*ans)

if __name__ == "__main__":
    solve()

The implementation begins by reducing all banknotes modulo $k$ and removing duplicates, since repeated identical transitions do not change reachability. The BFS maintains a queue of reachable residues and expands each by adding every distinct coin residue.

A subtle point is the use of modular addition with a conditional subtraction instead of % k, which avoids extra overhead in tight loops. The visited array ensures each residue is processed once, preventing quadratic blowup in repeated revisits.

Worked Examples

Example 1

Input:

2 8
12 20

Reduced residues: $12 \equiv 4$, $20 \equiv 4$. So only one move exists: +4 mod 8.

Step	Queue	Visited	Action
0	[0]	{0}	start
1	[]	{0}	from 0 add 4 → 4
2	[4]	{0,4}	process 4 → 4+4=0
3	[0]	{0,4}	already seen

Final visited residues are {0, 4}.

This matches the fact that all sums are multiples of 4, so only two residues modulo 8 appear.

Example 2

Input:

3 5
1 2 3

Residues are {1,2,3}. These already generate all residues modulo 5.

Step	Queue	Visited	Action
0	[0]	{0}	start
1	[1,2,3]	{0,1,2,3}	expand 0
2	...	{0,1,2,3,4}	further expansions fill 4

All residues become reachable.

This shows how combining multiple residues closes the graph into a full cycle space.

Complexity Analysis

Measure	Complexity	Explanation
Time	$O(k \cdot m)$	BFS over k states, each expanded using m distinct residues
Space	$O(k)$	visited array and queue over residues

Here $m$ is the number of distinct residues modulo $k$, bounded by $n$. In practice, both $k$ and $n$ are up to $10^5$, and each state is processed once, making the solution efficient under constraints.

Test Cases

import sys, io

def run(inp: str) -> str:
    sys.stdin = io.StringIO(inp)
    from collections import deque

    def solve():
        n, k = map(int, input().split())
        a = list(map(int, input().split()))

        mods = list(set(x % k for x in a))

        vis = [False] * k
        vis[0] = True
        q = deque([0])

        while q:
            r = q.popleft()
            for m in mods:
                nr = r + m
                if nr >= k:
                    nr -= k
                if not vis[nr]:
                    vis[nr] = True
                    q.append(nr)

        ans = [i for i in range(k) if vis[i]]
        return str(len(ans)) + "\n" + " ".join(map(str, ans))

    return solve()

# provided sample
assert run("2 8\n12 20\n") == "2\n0 4"

# minimum case
assert run("1 2\n1\n") == "2\n0 1"

# all same residue
assert run("3 6\n6 12 18\n") == "1\n0"

# full reachability
assert run("3 5\n1 2 3\n") == "5\n0 1 2 3 4"

# single coin not generating all
assert run("2 7\n2 4\n")  # sanity check structure

Test input	Expected output	What it validates
2 8 / 12 20	2 / 0 4	cyclic residue restriction
1 2 / 1	2 / 0 1	minimal full reachability
3 6 / 6 12 18	1 / 0	all multiples of modulus
3 5 / 1 2 3	5 / 0 1 2 3 4	full closure case

Edge Cases

When all denominations are divisible by $k$, every transition in the BFS becomes a self-loop at residue 0. The algorithm initializes with residue 0, and no new state is ever enqueued, so the output correctly becomes only {0}.

When there is a single denomination equal to 1, every residue becomes reachable. The BFS from 0 immediately expands to all nodes because repeated +1 steps traverse the entire cycle graph modulo $k$, eventually marking all residues as visited.

When denominations generate a proper subgroup of $\mathbb{Z}_k$, such as {2, 4} modulo 6, the BFS explores only that subgroup. Starting at 0, reachable states remain within even residues, and the algorithm never leaks into odd residues because every transition preserves parity.