P2025 Dirichlet Semi-Online Convolution

Given a function $f$ satisfying $f(1)=1$, and $$f(n)=\sum_{d|n,d

One line with a positive integer $n$.

One line with a non-negative integer, representing the value of $\bigoplus_{k=1}^n\left(f(k)\bmod 2^{32}\right)$.

For all testdata, $1 \le n \le 5 \times 10^7$. For Sample 1, the first $10$ terms of $f$ are: $1, 1, 2, 3, 4, 6, 6, 9, 10, 12$. The time limit is $1.5$ times that of std. Translated by ChatGPT 5