Core Logic and Mathematical Principles
Multiplicative Functions and Completely Multiplicative Functions
A function $f(n)$ is defined on the domain of positive integers. If for any pair of positive integers $a$ and $b$ such that $ ext{gcd}(a, b) = 1$, it holds that:
$$f(a \times b) = f(a) \times f(b)$$
then $f(n)$ is called a multiplicative function. If for any positive integers $a$ and $b$ (not necessarily coprime), it holds that $f(a \times b) = f(a) \times f(b)$, then $f(n)$ is called a completely multiplicative function.
Among the multiplicative functions frequently encountered in NOIP competitions are:
- Möbius Function $ u(n)$:
$$\nu(n) = \begin{cases} 1 & n = 1 \\ (-1)^k & n = p_1 p_2 \dots p_k \text{ (distinct prime factors)} \\ 0 & \exists p, p^2 \mid n \end{cases}$$
- Euler's Totient Function $ ext{φ}(n)$: This function counts the integers from $1$ to $n$ that are coprime to $n$. Its general formula is:
$$\text{φ}(n) = n \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right)$$
Core Mechanism of the Linear Sieve (Euler Sieve)
The Sieve of Eratosthenes has redundant operations that repeatedly mark composite numbers (for example, $6$ is marked once by $2$ and once by $3$), resulting in a time complexity of $O(N \log \log N)$. The linear sieve (Euler sieve) reduces the time complexity to an optimal $O(N)$ by ensuring that each composite number is marked only once by its smallest prime factor.
The core state is maintained by a scanning pointer $i$ and the current set of primes. When scanning to $i$, we iterate through the known primes $p_j$:
If $i \bmod p_j == 0$, since $p_j$ is traversed in ascending order, it implies that $p_j$ is the smallest prime factor of $i$. If we continue to mark $i \cdot p_{j+1}$, since $i$ contains the prime factor $p_j$, the smallest prime factor of $i \cdot p_{j+1}$ must be $p_j$, not $p_{j+1}$. To prevent duplicate marking, we must immediately break out of the loop.
State Design and Algorithm Derivation
Due to the special multiplicative property of multiplicative functions, we can deeply embed them into the execution flow of the linear sieve. While marking composite numbers, we can derive the current function value of the composite number using the predecessor state in $O(1)$ time complexity.
1. Linear Sieve State Derivation for the Möbius Function $
u(n)$
- Boundary: $ u(1) = 1$.
- Case A (when $i$ is prime): Since $i$ has only one prime factor, by definition $ u(i) = -1$.
- Case B (when $i \bmod p_j \neq 0$): Here, $p_j$ is coprime to $i$. By the property of multiplicative functions:
$$\nu(i \cdot p_j) = \nu(i) \cdot \nu(p_j) = -\nu(i)$$
- Case C (when $i \bmod p_j == 0$): In this case, $i \cdot p_j$ contains at least two identical prime factors $p_j$ (i.e., $p_j^2 \mid (i \cdot p_j)$). By definition, its value is directly zero:
$$\nu(i \cdot p_j) = 0$$
2. Linear Sieve State Derivation for Euler's Totient Function $ ext{φ}(n)$
- Boundary: $ ext{φ}(1) = 1$.
- Case A (when $i$ is prime): All integers from $1$ to $i-1$ are coprime to $i$, thus $ ext{φ}(i) = i - 1$.
- Case B (when $i \bmod p_j \neq 0$): $p_j$ is coprime to $i$, by the multiplicative property:
$$\text{φ}(i \cdot p_j) = \text{φ}(i) \cdot \text{φ}(p_j) = \text{φ}(i) \cdot (p_j - 1)$$
- Case C (when $i \bmod p_j == 0$): Here, $p_j$ is a factor of $i$, indicating that $i$ already includes all prime factor types of $i \cdot p_j$. Plugging into the general formula gives:
$$\text{φ}(i \cdot p_j) = (i \cdot p_j) \prod_{p \mid (i \cdot p_j)} \left(1 - \frac{1}{p}\right) = p_j \cdot \left[ i \prod_{p \mid i} \left(1 - \frac{1}{p}\right) \right] = p_j \cdot \text{φ}(i)$$
C++ Standard Source Code
#include <iostream>
#include <vector>
const int MAXN = 2000000; // Simulating the standard global scale of NOIP
int primes[MAXN + 5], cnt;
bool is_not_prime[MAXN + 5]; // Inverted state: false indicates prime, which helps save memset or default initialization time
int mu[MAXN + 5];
int phi[MAXN + 5];
void sieve(int n) {
is_not_prime[0] = is_not_prime[1] = true;
mu[1] = 1;
phi[1] = 1; // Must manually initialize boundary states
cnt = 0;
for (int i = 2; i <= n; ++i) {
if (!is_not_prime[i]) {
primes[cnt++] = i;
mu[i] = -1; // Prime has only one prime factor
phi[i] = i - 1; // The value of Euler's function for a prime is i - 1
}
for (int j = 0; j < cnt && i * primes[j] <= n; ++j) {
int target = i * primes[j];
is_not_prime[target] = true; // Mark composite numbers
if (i % primes[j] == 0) {
mu[target] = 0; // There exists a squared factor, the value of the Möbius function must be 0
phi[target] = phi[i] * primes[j]; // The types of prime factors remain unchanged, Euler's function directly multiplies by primes[j]
break; // Core of the linear sieve: ensure each composite is only sieved by its smallest prime factor
} else {
mu[target] = -mu[i]; // Coprime case, a new distinct prime factor is added, sign is inverted
phi[target] = phi[i] * (primes[j] - 1); // Coprime case, directly use multiplicative property to multiply
}
}
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int n;
if (std::cin >> n) {
if (n > MAXN) n = MAXN; // Defensive out-of-bounds interception
sieve(n);
// Output the first 10 results for verification
for (int i = 1; i <= std::min(n, 10); ++i) {
std::cout << "i=" << i << " | mu=" << mu[i] << " | phi=" << phi[i] << "\n";
}
}
return 0;
}NOIP Practical Pitfall Guide
- Missing
breakor Incorrect Placement in Linear Sieve Ifbreakis omitted in the condition branchi % primes[j] == 0, the composite number will be repeatedly sieved by subsequent larger prime factors. The algorithm's time complexity will degrade instantly to $O(N \log \log N)$ or even close to $O(N^2)$, resulting in a direct TLE (Time Limit Exceeded) under the NOIP limit of $10^7$. - Risk of Array Out-of-Bounds
In the inner loop, the control condition must strictly be written as
i * primes[j] <= n, and cannot rely solely onj < cntfor interception. If multiplication boundary restrictions are not applied,i * primes[j]may directly access out-of-bounds memory and alter it, leading to unpredictable segmentation faults or garbage values in calculations.
Classic NOIP/Luogu Real Problems
1. Luogu P3812 [Template] Linear Basis / Similar Number Theory Variant P2158 [SDOI2008] Honor Guard
- Problem Description: In an $N \times N$ square matrix, calculate the number of people visible from the bottom left corner $(0,0)$ (i.e., there are no other people obstructing the line connecting the two points).
- Core Essence of the Problem: Count the number of pairs $(x, y)$ such that $ ext{gcd}(x, y) = 1$.
- Core Solving Idea: Aside from the boundaries $(1,0)$ and $(0,1)$, the square matrix has symmetry. For one side, when the x-coordinate is $x$, the number of y-coordinates $y < x$ that are coprime to $x$ is exactly the definition of Euler's function $ ext{φ}(x)$. Therefore, the answer is fundamentally $3 + 2 \times \sum_{i=2}^{N-1} \text{φ}(i)$. Directly call the linear sieve to preprocess the entire $ ext{φ}$ array, then accumulate the prefix sum to break through in $O(N)$ time.
2. Luogu P3455 [POI2007] ZAP-Queries
- Problem Description: Given $a, b, d$, find the number of pairs $(x, y)$ such that $1 \le x \le a, 1 \le y \le b$ and $ ext{gcd}(x, y) = d$. Multiple queries.
- Core Essence of the Problem: Basic application of Möbius inversion.
- Core Solving Idea: Equivalent to finding $\sum_{i=1}^{\lfloor a/d \rfloor} \sum_{j=1}^{\lfloor b/d \rfloor} [\text{gcd}(i, j) == 1]$. By utilizing the property of the Möbius function $\sum_{d \mid n} \nu(d) = [n==1]$ for property replacement, the equation can ultimately be transformed into:
$$\sum_{T=1}^{\min(\lfloor a/d \rfloor, \lfloor b/d \rfloor)} \nu(T) \cdot \lfloor \frac{a}{d \cdot T} \rfloor \cdot \lfloor \frac{b}{d \cdot T} \rfloor$$
By preprocessing the $ u$ function with the linear sieve in $O(N)$ and establishing a prefix sum, combined with divisibility block techniques (number theory block), it can respond to a single query in $O(\sqrt{N})$ time.