Grade 12 · 9 algorithmsCitește în română

Math for programmingMatematică pentru programare

Every math for programming algorithm from the Romanian high school curriculum, with the idea explained, its complexity, examples and code you can edit and run right here.

Create a free account Browse the collection

9algorithms
6chapters
1grade

Math for programming

Matematică pentru programare · 9 algorithms

Smallest-prime-factor sieve and fast factorizationCiur cu cel mai mic divizor prim și factorizare rapidăA variant of the Sieve of Eratosthenes: instead of only marking 'composite', we store in dp[x] the smallest prime divisor of x. For every prime p…O(log n)
Combinations modulo a primeCombinări modulo un număr primWe compute C(n, k) mod P, with P = 1,000,000,007 (prime) and n ≤ 10^6. We have C(n, k) = n! / (k! * (n-k)!), but division cannot be done directly on…O(log n)
Extended Euclidean algorithmAlgoritmul lui Euclid extinsBesides d = gcd(a, b), we find integers x and y with a * x + b * y = d. If b = 0, then d = a, x = 1, y = 0. Otherwise we solve recursively for (b, a…O(log n)
Modular exponentiationExponențierea modularăWe compute a^n mod m for n up to 10^18. We use the same idea as fast exponentiation, but after every multiplication we take the remainder modulo m:…O(log n)
Fast exponentiationExponențierea rapidăWe compute a^n with about log2(n) multiplications instead of n. The idea: a^n = (a^2)^(n/2) if n is even and a^n = a * a^(n-1) if n is odd. The…O(log n)
Number and sum of divisors from the prime factorizationNumărul și suma divizorilor din descompunerea în factori primiIf n = p1^e1 * p2^e2 * ... * pk^ek, a divisor chooses for every prime an exponent between 0 and ei, so the number of divisors is (e1 + 1) * (e2 + 1)…O(√n)
Number of multiples of k in a rangeNumărul multiplilor lui k dintr-un intervalHow many numbers in [a, b] are divisible by k? The numbers in [1, x] divisible by k are k, 2k, ..., (x / k) * k, i.e. x / k of them (integer…O(log n)
Sum of an arithmetic progression: formula vs. loopSuma unei progresii aritmetice: formulă vs. buclăThe progression has first term a, common difference r and n terms: a, a + r, ..., a + (n-1) * r. The loop adds the terms one by one, so it takes n…O(1)
Pascal's triangle (combinations)Triunghiul lui Pascal (combinări)The combinations C(i, j), the number of j-element subsets of an i-element set, satisfy C(i, j) = C(i-1, j-1) + C(i-1, j): either we choose element…O(n²)