已发布·持续改进
数学与数论 指南 · 2/6
本章目前仅提供英文版。
This chapter traces each algorithm on small numbers. Following the tables by hand is the fastest way to see why the code looks the way it does.
Let r be the remainder of a divided by b. Because r = a - q × b, every common divisor of a and b also divides r, and vice versa. So replacing (a, b) with (b, r) keeps the GCD unchanged while the numbers keep shrinking.
| Step | a | b | a mod b |
|---|---|---|---|
| 1 | 252 | 105 | 42 |
| 2 | 105 | 42 | 21 |
| 3 | 42 | 21 | 0 |
The remainder hits 0 at step 3, so the answer is the b of that row: 21. Three steps in total.
def gcd(a: int, b: int) -> int:
while b:
a, b = b, a % b
return a
print(gcd(252, 105)) # 21The extended version tracks, next to each remainder r, the coefficients x and y that express it as 240 × x + 46 × y. Every time a quotient q is produced, all three values follow the same rule: new = previous - q × current.
| q | r | x | y |
|---|---|---|---|
| - | 240 | 1 | 0 |
| - | 46 | 0 | 1 |
| 5 | 10 | 1 | -5 |
| 4 | 6 | -4 | 21 |
| 1 | 4 | 5 | -26 |
| 1 | 2 | -9 | 47 |
| 2 | 0 | 23 | -120 |
The answer is the row just before the remainder becomes 0: gcd = 2, x = -9, y = 47, and indeed 240 × (-9) + 46 × 47 = -2160 + 2162 = 2. Check that 240 × x + 46 × y = r holds on every row. That invariant is exactly why the algorithm is correct.
def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
old_r, r = a, b
old_x, x = 1, 0
old_y, y = 0, 1
while r:
q = old_r // r
old_r, r = r, old_r - q * r
old_x, x = x, old_x - q * x
old_y, y = y, old_y - q * y
return old_r, old_x, old_y
print(extended_gcd(240, 46)) # (2, -9, 47)Instead of twelve multiplications, look at the exponent in binary. 13 = 1101 (base 2) = 8 + 4 + 1, so 3^13 = 3^8 × 3^4 × 3^1. Keep squaring the base (3, 3^2, 3^4, 3^8, …) and multiply it into the result only where the exponent has a 1 bit.
| exp (binary) | lowest bit | result | base (for next step) |
|---|---|---|---|
| 1101 | 1 | 1 × 3 = 3 | 3^2 = 9 ≡ 2 |
| 110 | 0 | 3 | 2^2 = 4 |
| 11 | 1 | 3 × 4 = 12 ≡ 5 | 4^2 = 16 ≡ 2 |
| 1 | 1 | 5 × 2 = 10 ≡ 3 | 2^2 = 4 |
The answer is 3. Fermat's little theorem confirms it: 3^6 ≡ 1 (mod 7), so 3^13 = (3^6)^2 × 3 ≡ 3. The number of multiplications is proportional to the number of bits in the exponent, so even an exponent of 10^18 needs only about 60 iterations.
Walk upward from 2. Whenever you meet a number that has not been crossed out, it is prime, and you cross out all of its multiples. It is enough to start at i × i: any smaller multiple i × k with k < i was already crossed out while processing the smaller factor k.
| i | newly crossed out |
|---|---|
| 2 | 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30 |
| 3 | 9, 15, 21, 27 (12, 18, 24 and 30 are already gone) |
| 4 | already crossed out, skip |
| 5 | 25 (30 is already gone) |
| 6 | 6 × 6 = 36 exceeds 30, stop |
What remains is 2, 3, 5, 7, 11, 13, 17, 19, 23, 29: ten primes. The outer loop only runs while i × i ≤ n, so for 30 the work is effectively done at i = 5.
The simplest factorization method is trial division up to √n. For 360, divide by 2 three times (360, 180, 90, 45), then by 3 twice (45, 15, 5). The leftover 5 has no divisor up to √5, so it is prime, and 360 = 2^3 × 3^2 × 5.
A binomial coefficient C(n, r) = n! / (r! × (n - r)!) modulo a prime p cannot be computed by plain division. Instead you multiply by the inverse of the denominator. Inverting with Fermat's little theorem gives C(n, r) ≡ n! × (r!)^(p-2) × ((n-r)!)^(p-2) (mod p) when n < p.
p = 10**9 + 7
def ncr_mod(n: int, r: int) -> int:
if r < 0 or r > n:
return 0
num = den = 1
for i in range(r):
num = num * (n - i) % p
den = den * (i + 1) % p
return num * pow(den, p - 2, p) % p
print(ncr_mod(10, 3)) # 120
print(ncr_mod(100000, 50000)) # 149033233 — the exact value has over 30,000 digitsThe Euclidean algorithm shrinks big numbers by replacing them with remainders, and the extended version carries the Bezout coefficients along. Fast exponentiation uses the binary form of the exponent to cut the number of multiplications to a logarithm. The sieve crosses out multiples starting at i × i to find every prime in a range at once, and nCr mod p multiplies by inverses instead of dividing. The next chapter turns all of this into reusable code.
0 条评论
登录 · 登录后即可发表评论。
来发表第一条评论吧。