1.1 Basic Sieve Approach
The fundamental strategy involves iterating through integers starting from 2 and marking all their multiples as composite. Because a prime number is divisible only by 1 and itself, it remains unmarked. The total operations correspond to the sum of the harmonic series ($\frac{n}{2} + \frac{n}{3} + \dots$), yielding a time complexity of $O(n \log n)$.
static const int MAX_LIMIT = 100005;
std::vector<bool> isComposite(MAX_LIMIT, false);
std::vector<int> primes;
void initializePrimes(int limit) {
for (int i = 2; i <= limit; ++i) {
if (!isComposite[i]) {
primes.push_back(i);
}
for (long long j = 1LL * i * i; j <= limit; j += i) {
isComposite[j] = true;
}
}
}</int></bool>
1.2 Optimized Basic Sieve
In the basic version, numbers like 36 are repeatedly marked by multiple factors (e.g., 2, 3, 4, 6, 9...). Since multiplication is commutative ($a \times b = b \times a$), we can optimize by iterating until the square root of the limit. We start marking multiples from $i^2$ onwards, reducing redundant checks while maintaining the same asymptotic complexity but improving the constant factor.
void optimizedInitialize(int limit) {
int threshold = static_cast<int>(std::sqrt(limit)) + 1;
// Clear state if reused
// std::fill(isComposite.begin(), isComposite.end(), false);
// primes.clear();
for (int i = 2; i <= threshold; ++i) {
if (!isComposite[i]) {
// Mark starting from i*i
for (long long j = 1LL * i * i; j <= limit; j += i) {
isComposite[j] = true;
}
}
}
// Collect remaining non-composite numbers
for (int i = 2; i <= limit; ++i) {
if (!isComposite[i]) {
primes.push_back(i);
}
}
}</int>
1.3 Linear Sieve (Euler's Sieve)
To achieve $O(n)$ complexity, we ensure every composite number is visited exactly once. A number $x$ is uniquely identified by its smallest prime factor $p$. During iteration, if $i$ is a prime, we record it. Then, we iterate through existing primes to mark $i \times p_j$. Crucially, if $i$ is divisible by $p_j$, we stop. This guarantees $p_j$ remains the smallest prime factor for future composites formed by $i$.
void linearSieve(int limit) {
std::fill(isComposite.begin(), isComposite.end(), false);
primes.clear();
for (int i = 2; i <= limit; ++i) {
if (!isComposite[i]) {
primes.push_back(i);
}
for (size_t j = 0; j < primes.size(); ++j) {
long long val = 1LL * i * primes[j];
if (val > limit) break;
isComposite[val] = true;
// If i contains the prime factor primes[j],
// then primes[j] is the smallest prime factor of val.
// Further iteration would find a smaller factor for subsequent products.
if (i % primes[j] == 0) break;
}
}
}
- Greatest Common Diviser (GCD)
2.1 Subtraction Method
The Euclidean algorithm via subtraction relies on the property $\gcd(a, b) = \gcd(a-b, b)$ assuming $a > b$. By repeatedly subtracting the smaller number from the larger one, we eventually reach a state where one number becomes zero, leaving the other as the GCD. This works because the greatest common divisor remains invariant under subtraction.
int gcd_subtraction(int a, int b) {
while (a != b) {
if (a > b) {
a -= b;
} else {
b -= a;
}
}
return a;
}
2.2 Division Method (Modulo)
Repeated subtraction is inefficient for large inputs. Using the modulo operator ($a \% b$) condenses multiple subtractions into a single step. The remainder operation effectively performs $a - k \times b$. The iterative approach or recursion yields logarithmic time complexity $O(\log(\min(a, b)))$.
int gcd_division(int a, int b) {
while (a && b) {
if (a > b) {
a %= b;
} else {
b %= a;
}
}
return a + b; // One is zero, sum gives the non-zero value
}
// Recursive variant
int euclid(int x, int y) {
return y == 0 ? x : euclid(y, x % y);
}
- Extended Euclidean Algorithm
This method solves linear Diophantine equations of the form $ax + by = c$. It extends the standard GCD computation to find coefficients $x$ and $y$ such that $ax + by = \gcd(a, b)$.
3.1 Existance of Solutions
A solution exists if and only if $c$ is a multiple of $\gcd(a, b)$. Since the linear combination of $a$ and $b$ always results in a multiple of their GCD, if the target $c$ shares this divisibility property, integer solutions exist. We can reduce the equation by dividing all terms by $\gcd(a, b)$ to find a base solution.
3.2 Particular and General Solutions
We first solve $ax + by = g$ where $g = \gcd(a, b)$. If $g | c$, the particular solution for the original equation is scaled by $c/g$. Through back-substitution during the recursive GCD calls, we derive the coefficients. If $(x_0, y_0)$ is a particular solution, the general solution is given by:
// Returns d = gcd(a,b) and finds x, y such that ax + by = d
int extended_gcd(int a, int b, int &x, int &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
int x1, y1;
int d = extended_gcd(b, a % b, x1, y1);
// Backtrack to update x and y
x = y1;
y = x1 - (a / b) * y1;
return d;
}
- Permutations and Combinations
4.1 Definitions
A Permutation refers to arranging $m$ elements chosen from $n$ distinct items where order matters. Denoted as $A_n^m$ or $P(n, m)$.
Formula: $A_n^m = \frac{n!}{(n-m)!}$.
A Combination refers to selecting $m$ elements from $n$ distinct items where order does not matter. Denoted as $C_n^m$ or $\binom{n}{m}$.
Formula: $C_n^m = \frac{n!}{m!(n-m)!}$.
4.2 Fundamental Relations
The relationship between permutations and combinations accounts for the arrangement of selected items:
4.3 Binomial Theorem
Expanding powers of binomials follows this pattern:
Inversion formulas allow switching between sequences related by summation. If $f_n = \sum_{i=0}^n \binom{n}{i} g_i$, then:
4.5 Applications
At Least vs. Exactly:
If $f_k$ represents the count for exactly $k$ items and $g_k$ represents at least $k$, the conversion is: