Detailed mathematical approach

Problem Summary

For each pile size \(n\), one move chooses a number \(a\) with \(1 \le a \le n\) and \(\gcd(a,n)=1\), then replaces the pile by \(n-a\). For fixed \(N\) and \(K\), we consider ordered \(K\)-tuples of pile sizes drawn from \(\{1,2,\dots,N-1\}\). The task is to count how many such \(K\)-pile positions are losing positions, meaning that the xor of their Grundy values is \(0\), and to return the answer modulo \(10^9+7\).

A direct dynamic program over all \(K\)-pile states is hopeless for the intended input size, so the solution first classifies the one-pile game completely and then turns the multi-pile count into an xor convolution problem.

Mathematical Approach

Let \(g(n)\) be the Grundy value of one pile of size \(n\). The move rule gives

$g(n)=\operatorname{mex}\left\{g(n-a): 1 \le a \le n,\ \gcd(a,n)=1\right\}.$

If we know the distribution of these one-pile Grundy values on \(\{1,\dots,N-1\}\), then Sprague-Grundy theory reduces the full problem to counting xor sums.

Step 1: Express the Game in Sprague-Grundy Form

The position with \(K\) piles \((x_1,\dots,x_K)\) is losing exactly when

$g(x_1)\oplus g(x_2)\oplus \cdots \oplus g(x_K)=0.$

So the main difficulty is to understand \(g(n)\) for one pile. Once that is known, each pile contributes only its Grundy label, and the counting problem becomes purely combinatorial.

Step 2: Classify the One-Pile Grundy Values

The implementations use the closed form

$g(1)=1,$

$g(n)=0 \quad \text{for even } n,$

$g(n)=\pi(\operatorname{spf}(n)) \quad \text{for odd } n>1,$

where \(\operatorname{spf}(n)\) is the smallest prime factor of \(n\), and \(\pi(t)\) is the number of primes at most \(t\), so for a prime \(p\), \(\pi(p)\) is its \(1\)-based prime index.

This formula follows from the move structure:

For \(n=1\), the only legal move is to \(0\), so the mex is \(1\).

If \(n\) is even, every legal \(a\) must be odd, hence every reachable value \(n-a\) is a positive odd number. Every positive odd number has positive Grundy value, so \(0\) is missing from the move set and therefore \(g(n)=0\).

Now let \(n>1\) be odd and write \(p=\operatorname{spf}(n)\). The move \(a=1\) reaches \(n-1\), which is even, so Grundy value \(0\) is present. The move \(a=n-1\) reaches \(1\), so Grundy value \(1\) is present. More generally, for every odd prime \(q<p\), the move to the pile \(q\) is legal because

$\gcd(n,n-q)=\gcd(n,q)=1,$

since \(q\) does not divide \(n\). That target has Grundy value \(\pi(q)\). Hence every value below \(\pi(p)\) occurs among the legal moves.

On the other hand, no legal move can land on an odd number whose smallest prime factor is exactly \(p\). If such a target \(m\) existed, then \(p\mid n\) and \(p\mid m\), so

$\gcd(n,n-m)=\gcd(n,m)\ge p,$

contradicting the coprimality condition on the move. Therefore Grundy value \(\pi(p)\) is absent, and the mex is exactly \(\pi(p)\).

Larger Grundy values may also appear among some moves, but they do not matter once all smaller values are present and \(\pi(p)\) is missing.

Step 3: Build the Frequency Table of Grundy Values

Define

$c_t=\#\left\{x\in\{1,\dots,N-1\}: g(x)=t\right\}.$

Then \(c_t\) is the number of pile sizes carrying Grundy label \(t\). The classification above immediately implies

$c_0=\left\lfloor\frac{N-1}{2}\right\rfloor,$

because exactly the even pile sizes have Grundy value \(0\), and

$c_1=1,$

because the only pile with Grundy value \(1\) is \(1\) itself. Every odd \(x>1\) contributes to the bucket indexed by the prime index of its smallest prime factor.

The implementations obtain these buckets with a linear sieve that stores the smallest prime factor of every integer up to \(N-1\), together with the running prime-count function \(\pi\).

Step 4: Turn \(K\) Piles into an XOR Convolution

Let \(L(N,K)\) denote the number of losing ordered \(K\)-tuples. If one pile contributes Grundy value \(u\) in \(c_u\) ways and another contributes \(v\) in \(c_v\) ways, then the pair contributes xor value \(u\oplus v\). This is exactly xor convolution.

For two arrays \(f\) and \(h\), define

$\left(f *_{\oplus} h\right)(s)=\sum_{u\oplus v=s} f(u)h(v).$

Therefore the distribution of xor sums for \(K\) piles is the \(K\)-fold xor convolution of \(c\) with itself, and the desired answer is

$L(N,K)=c^{(*K)}(0).$

This identity is just Sprague-Grundy theory translated into counting language: pile choices are independent, and a position is losing exactly when the xor sum is \(0\).

Step 5: Evaluate the XOR Convolution with the Walsh-Hadamard Transform

Directly forming \(K\) xor convolutions would still be too slow, so the implementations switch to the Walsh-Hadamard transform for xor convolution. If \(\widehat{c}\) denotes the xor transform of \(c\), then

$\widehat{c^{(*K)}}(i)=\widehat{c}(i)^K.$

So the whole computation becomes:

Pad the frequency vector to a power-of-two length \(m\).

Apply the xor Walsh-Hadamard transform.

Raise each transformed component to the \(K\)-th power modulo \(10^9+7\).

Apply the same transform again.

Multiply every entry by \(m^{-1}\pmod{10^9+7}\), because for xor convolution the transform is self-inverse up to the factor \(m\).

The coefficient at index \(0\) is then exactly \(L(N,K)\).

Worked Example: \(L(5,2)\)

For \(N=5\), the allowed pile sizes are \(1,2,3,4\). Their Grundy values are

$g(1)=1,\qquad g(2)=0,\qquad g(3)=2,\qquad g(4)=0.$

Hence the frequency vector is

$c_0=2,\qquad c_1=1,\qquad c_2=1.$

With two piles, xor is \(0\) exactly when both piles have the same Grundy value, so

$L(5,2)=c_0^2+c_1^2+c_2^2=2^2+1^2+1^2=6.$

This matches the checkpoint used by the implementation and illustrates why the entire problem is governed by the Grundy frequency distribution rather than by the raw pile values.

How the Code Works

The C++, Python, and Java implementations follow the same pipeline. First they build a linear sieve up to \(N-1\), storing for every number its smallest prime factor and also the prime-count prefix needed to convert a smallest prime factor into its prime index. Then they construct the Grundy frequency vector directly from the closed form above: all even sizes contribute to Grundy \(0\), the pile \(1\) contributes to Grundy \(1\), and every odd size greater than \(1\) is placed into the bucket determined by the prime index of its smallest prime factor.

Next the implementation copies that frequency vector into a power-of-two buffer and applies the xor Walsh-Hadamard transform. Each transformed coefficient is raised to the \(K\)-th power modulo \(10^9+7\). After the inverse scaling step, the entry at index \(0\) is the number of losing positions. The C++ implementation also includes small brute-force cross-checks and fixed checkpoints to verify the closed form and the convolution result on manageable inputs, while keeping the main large-instance computation entirely in the fast pipeline.

Complexity Analysis

Let \(L=N-1\), and let \(m\) be the smallest power of two with \(m\ge \pi(L)+1\). The linear sieve and the frequency construction take \(O(L)\) time. The Walsh-Hadamard transform takes \(O(m\log m)\) time, and the pointwise exponentiation takes \(O(m\log K)\) time because each coefficient is raised by binary exponentiation. The total memory usage is \(O(L+m)\), dominated in practice by the sieve arrays.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=560
2. Sprague-Grundy theorem: Wikipedia - Sprague-Grundy theorem
3. Mex: Wikipedia - Mex (mathematics)
4. Hadamard transform: Wikipedia - Hadamard transform
5. Linear sieve: cp-algorithms - Linear Sieve