Lançado · em melhoria
Guia de Matemática e teoria dos números · 5/6
Por enquanto, este capítulo está disponível apenas em inglês.
These problems were written to exercise each tool from the earlier chapters in turn. Try to work out an approach on your own before reading the solution.
A rectangular floor measures W by H centimeters (integers). You want to cover it with identical square tiles, leaving no gaps and cutting no tiles. Find the side of the largest possible tile and how many tiles you need. Example: W = 120, H = 84 gives side 12 and 70 tiles.
Approach: the tile side must divide both W and H, so it is a common divisor, and the largest one is the GCD. The tile count is (W / g) × (H / g).
import math
def largest_tile(w: int, h: int) -> tuple[int, int]:
g = math.gcd(w, h)
return g, (w // g) * (h // g)
print(largest_tile(120, 84)) # (12, 70)
print(largest_tile(7, 5)) # (1, 35)There are k signal lights, and light i blinks once every p_i seconds. All of them blinked together at time 0. How many moments from second 1 to second T (inclusive) have every light blinking at once? Each p_i is at most 10^9, k is at most 10^5, and T is at most 10^18.
Approach: the lights all blink together exactly at common multiples of every period, so the answer is T // lcm(p_1, …, p_k). Fold the LCM with lcm(a, b) = a // gcd(a, b) * b. As soon as the LCM exceeds T the answer is 0, so stop early. That early exit also makes the code easy to port to C++ or Java without overflow.
import math
def simultaneous_blinks(periods: list[int], t: int) -> int:
l = 1
for p in periods:
l = l // math.gcd(l, p) * p
if l > t:
return 0
return t // l
print(simultaneous_blinks([4, 6, 10], 300)) # 5 (60, 120, 180, 240, 300)
print(simultaneous_blinks([7, 11, 13], 1000)) # 0 (lcm = 1001)You get Q queries, each a pair L R with 1 ≤ L ≤ R ≤ 10^6. For each, print how many primes lie between L and R inclusive. Q can be as large as 10^5.
Approach: testing primality per query is too slow. Sieve once up to 10^6, build the prefix sum prefix[x] = number of primes ≤ x, and answer each query in O(1) as prefix[R] - prefix[L - 1].
def build_prime_prefix(limit: int) -> list[int]:
is_prime = bytearray([1]) * (limit + 1)
is_prime[0] = is_prime[1] = 0
i = 2
while i * i <= limit:
if is_prime[i]:
is_prime[i * i :: i] = bytes((limit - i * i) // i + 1)
i += 1
prefix = [0] * (limit + 1)
running = 0
for x in range(limit + 1):
running += is_prime[x]
prefix[x] = running
return prefix
prefix = build_prime_prefix(10**6)
for left, right in [(1, 10), (10, 30), (1, 10**6)]:
print(prefix[right] - prefix[left - 1]) # 4, 6, 78498On an R × C grid, count the paths from the top-left corner to the bottom-right corner that move only right or down, one unit at a time, modulo 10^9 + 7. There are up to 10^5 queries, with R + C ≤ 2 × 10^5.
Approach: every path makes R + C moves, R of them downward, so the answer is C(R + C, R). Precompute factorials and inverse factorials up to the maximum and each query costs two multiplications.
MOD = 10**9 + 7
LIMIT = 2 * 10**5
fact = [1] * (LIMIT + 1)
for i in range(1, LIMIT + 1):
fact[i] = fact[i - 1] * i % MOD
inv_fact = [1] * (LIMIT + 1)
inv_fact[LIMIT] = pow(fact[LIMIT], MOD - 2, MOD)
for i in range(LIMIT, 0, -1):
inv_fact[i - 1] = inv_fact[i] * i % MOD
def ncr(n: int, r: int) -> int:
if r < 0 or r > n:
return 0
return fact[n] * inv_fact[r] % MOD * inv_fact[n - r] % MOD
print(ncr(2 + 2, 2)) # 6
print(ncr(3 + 7, 3)) # 120
print(ncr(100000 + 100000, 100000)) # 879467333Given integers a, b and m (m ≥ 1), find every x with 0 ≤ x < m such that a × x ≡ b (mod m). Return an empty list if there is none.
Approach: with g = gcd(a, m), the equation a × x - m × y = b has integer solutions exactly when g divides b. If it does, divide through by g to get (a/g) × x ≡ (b/g) (mod m/g). Now a/g and m/g are coprime, so an inverse yields one solution x0, and the full set is x0 + k × (m/g) for k = 0 … g-1.
def gcd_with_coeff(a: int, b: int) -> tuple[int, int]:
"""Return (g, x) with a * x ≡ g (mod b), where g = gcd(a, b)."""
old_r, r, old_x, x = a, b, 1, 0
while r:
q = old_r // r
old_r, r = r, old_r - q * r
old_x, x = x, old_x - q * x
return old_r, old_x
def solve_linear_congruence(a: int, b: int, m: int) -> list[int]:
a, b = a % m, b % m
g, x = gcd_with_coeff(a, m)
if b % g != 0:
return []
step = m // g
x0 = (x * (b // g)) % step
return [x0 + k * step for k in range(g)]
print(solve_linear_congruence(14, 30, 100)) # [45, 95]
print(solve_linear_congruence(4, 3, 6)) # [] — gcd 2 does not divide 3
print(solve_linear_congruence(3, 1, 7)) # [5] — the inverse of 3The y coefficient is not needed here, so the extended Euclid loop tracks only x. Since a × x ≡ g (mod m), multiplying by b / g gives a × x ≡ b. Reducing modulo step at the end yields the smallest solution.
Reach for the GCD when something must be split into equal parts, the LCM when cycles must line up, a sieve plus prefix sums for repeated prime queries over a range, factorial tables for repeated binomial coefficients, and extended Euclid for inverses and congruences. A good habit: first decide which tool the problem needs, then check the input limits for overflow and time.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.