21_number_theory.py

Download
python 438 lines 10.9 KB 
  1"""
  2μˆ˜ν•™κ³Ό μ •μˆ˜λ‘  (Number Theory)
  3Number Theory Algorithms
  4
  5μ •μˆ˜λ‘ μ˜ κΈ°λ³Έ μ•Œκ³ λ¦¬μ¦˜μ„ κ΅¬ν˜„ν•©λ‹ˆλ‹€.
  6"""
  7
  8from typing import List, Tuple
  9from functools import reduce
 10import math
 11
 12
 13# =============================================================================
 14# 1. GCD / LCM
 15# =============================================================================
 16
 17def gcd(a: int, b: int) -> int:
 18    """
 19    μ΅œλŒ€κ³΅μ•½μˆ˜ (μœ ν΄λ¦¬λ“œ ν˜Έμ œλ²•)
 20    μ‹œκ°„λ³΅μž‘λ„: O(log(min(a, b)))
 21    """
 22    while b:
 23        a, b = b, a % b
 24    return a
 25
 26
 27def lcm(a: int, b: int) -> int:
 28    """μ΅œμ†Œκ³΅λ°°μˆ˜"""
 29    return a * b // gcd(a, b)
 30
 31
 32def gcd_multiple(numbers: List[int]) -> int:
 33    """μ—¬λŸ¬ 수의 GCD"""
 34    return reduce(gcd, numbers)
 35
 36
 37def lcm_multiple(numbers: List[int]) -> int:
 38    """μ—¬λŸ¬ 수의 LCM"""
 39    return reduce(lcm, numbers)
 40
 41
 42def extended_gcd(a: int, b: int) -> Tuple[int, int, int]:
 43    """
 44    ν™•μž₯ μœ ν΄λ¦¬λ“œ μ•Œκ³ λ¦¬μ¦˜
 45    gcd(a, b) = a*x + b*yλ₯Ό λ§Œμ‘±ν•˜λŠ” (gcd, x, y) λ°˜ν™˜
 46    """
 47    if b == 0:
 48        return a, 1, 0
 49
 50    g, x1, y1 = extended_gcd(b, a % b)
 51    x = y1
 52    y = x1 - (a // b) * y1
 53
 54    return g, x, y
 55
 56
 57# =============================================================================
 58# 2. μ†Œμˆ˜ (Prime Numbers)
 59# =============================================================================
 60
 61def is_prime(n: int) -> bool:
 62    """
 63    μ†Œμˆ˜ νŒλ³„
 64    μ‹œκ°„λ³΅μž‘λ„: O(√n)
 65    """
 66    if n < 2:
 67        return False
 68    if n == 2:
 69        return True
 70    if n % 2 == 0:
 71        return False
 72
 73    for i in range(3, int(n ** 0.5) + 1, 2):
 74        if n % i == 0:
 75            return False
 76    return True
 77
 78
 79def sieve_of_eratosthenes(n: int) -> List[int]:
 80    """
 81    μ—λΌν† μŠ€ν…Œλ„€μŠ€μ˜ 체
 82    n μ΄ν•˜μ˜ λͺ¨λ“  μ†Œμˆ˜ λ°˜ν™˜
 83    μ‹œκ°„λ³΅μž‘λ„: O(n log log n)
 84    """
 85    if n < 2:
 86        return []
 87
 88    is_prime_arr = [True] * (n + 1)
 89    is_prime_arr[0] = is_prime_arr[1] = False
 90
 91    for i in range(2, int(n ** 0.5) + 1):
 92        if is_prime_arr[i]:
 93            for j in range(i * i, n + 1, i):
 94                is_prime_arr[j] = False
 95
 96    return [i for i in range(n + 1) if is_prime_arr[i]]
 97
 98
 99def prime_factorization(n: int) -> List[Tuple[int, int]]:
100    """
101    μ†ŒμΈμˆ˜λΆ„ν•΄
102    λ°˜ν™˜: [(μ†Œμˆ˜, μ§€μˆ˜), ...]
103    μ‹œκ°„λ³΅μž‘λ„: O(√n)
104    """
105    factors = []
106    d = 2
107
108    while d * d <= n:
109        if n % d == 0:
110            count = 0
111            while n % d == 0:
112                n //= d
113                count += 1
114            factors.append((d, count))
115        d += 1
116
117    if n > 1:
118        factors.append((n, 1))
119
120    return factors
121
122
123# =============================================================================
124# 3. λͺ¨λ“ˆλŸ¬ μ—°μ‚° (Modular Arithmetic)
125# =============================================================================
126
127def mod_pow(base: int, exp: int, mod: int) -> int:
128    """
129    λΉ λ₯Έ κ±°λ“­μ œκ³± (λͺ¨λ“ˆλŸ¬)
130    μ‹œκ°„λ³΅μž‘λ„: O(log exp)
131    """
132    result = 1
133    base %= mod
134
135    while exp > 0:
136        if exp % 2 == 1:
137            result = (result * base) % mod
138        exp //= 2
139        base = (base * base) % mod
140
141    return result
142
143
144def mod_inverse(a: int, mod: int) -> int:
145    """
146    λͺ¨λ“ˆλŸ¬ 역원 (modκ°€ μ†Œμˆ˜μΌ λ•Œ)
147    a^(-1) mod p = a^(p-2) mod p (페λ₯΄λ§ˆ μ†Œμ •λ¦¬)
148    """
149    return mod_pow(a, mod - 2, mod)
150
151
152def mod_inverse_extended(a: int, mod: int) -> int:
153    """
154    λͺ¨λ“ˆλŸ¬ 역원 (ν™•μž₯ μœ ν΄λ¦¬λ“œ)
155    gcd(a, mod) = 1일 λ•Œλ§Œ 쑴재
156    """
157    g, x, _ = extended_gcd(a, mod)
158    if g != 1:
159        return -1  # 역원 μ—†μŒ
160    return x % mod
161
162
163# =============================================================================
164# 4. μ‘°ν•©λ‘  (Combinatorics)
165# =============================================================================
166
167def factorial_mod(n: int, mod: int) -> int:
168    """n! mod p"""
169    result = 1
170    for i in range(2, n + 1):
171        result = (result * i) % mod
172    return result
173
174
175class Combination:
176    """
177    μ‘°ν•© 계산 (λͺ¨λ“ˆλŸ¬)
178    μ „μ²˜λ¦¬: O(n)
179    쿼리: O(1)
180    """
181
182    def __init__(self, n: int, mod: int):
183        self.mod = mod
184        self.fact = [1] * (n + 1)
185        self.inv_fact = [1] * (n + 1)
186
187        # νŒ©ν† λ¦¬μ–Ό 계산
188        for i in range(1, n + 1):
189            self.fact[i] = self.fact[i - 1] * i % mod
190
191        # μ—­ νŒ©ν† λ¦¬μ–Ό 계산
192        self.inv_fact[n] = mod_pow(self.fact[n], mod - 2, mod)
193        for i in range(n - 1, -1, -1):
194            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % mod
195
196    def nCr(self, n: int, r: int) -> int:
197        """nCr mod p"""
198        if r < 0 or r > n:
199            return 0
200        return self.fact[n] * self.inv_fact[r] % self.mod * self.inv_fact[n - r] % self.mod
201
202    def nPr(self, n: int, r: int) -> int:
203        """nPr mod p"""
204        if r < 0 or r > n:
205            return 0
206        return self.fact[n] * self.inv_fact[n - r] % self.mod
207
208
209# =============================================================================
210# 5. 였일러 ν”Ό ν•¨μˆ˜ (Euler's Totient)
211# =============================================================================
212
213def euler_phi(n: int) -> int:
214    """
215    Ο†(n) = n보닀 μž‘κ±°λ‚˜ κ°™κ³  nκ³Ό μ„œλ‘œμ†ŒμΈ μ–‘μ˜ μ •μˆ˜μ˜ 개수
216    μ‹œκ°„λ³΅μž‘λ„: O(√n)
217    """
218    result = n
219
220    d = 2
221    while d * d <= n:
222        if n % d == 0:
223            while n % d == 0:
224                n //= d
225            result -= result // d
226        d += 1
227
228    if n > 1:
229        result -= result // n
230
231    return result
232
233
234def euler_phi_sieve(n: int) -> List[int]:
235    """1~nκΉŒμ§€μ˜ 였일러 ν”Ό ν•¨μˆ˜ κ°’ (체)"""
236    phi = list(range(n + 1))
237
238    for i in range(2, n + 1):
239        if phi[i] == i:  # iκ°€ μ†Œμˆ˜
240            for j in range(i, n + 1, i):
241                phi[j] -= phi[j] // i
242
243    return phi
244
245
246# =============================================================================
247# 6. μ€‘κ΅­μΈμ˜ λ‚˜λ¨Έμ§€ 정리 (CRT)
248# =============================================================================
249
250def chinese_remainder_theorem(remainders: List[int], moduli: List[int]) -> int:
251    """
252    x ≑ r_i (mod m_i)λ₯Ό λ§Œμ‘±ν•˜λŠ” μ΅œμ†Œ μ–‘μ˜ μ •μˆ˜ x
253    λͺ¨λ“  m_iλŠ” μ„œλ‘œμ†Œμ—¬μ•Ό 함
254    """
255    M = 1
256    for m in moduli:
257        M *= m
258
259    result = 0
260    for r, m in zip(remainders, moduli):
261        Mi = M // m
262        yi = mod_inverse_extended(Mi, m)
263        result += r * Mi * yi
264
265    return result % M
266
267
268# =============================================================================
269# 7. 이항 κ³„μˆ˜ (Lucas Theorem)
270# =============================================================================
271
272def lucas(n: int, r: int, p: int) -> int:
273    """
274    루카슀 μ •λ¦¬λ‘œ nCr mod p 계산
275    pκ°€ μ†Œμˆ˜μΌ λ•Œ, n, r이 맀우 클 λ•Œ 유용
276    """
277    if r == 0:
278        return 1
279    return lucas(n // p, r // p, p) * nCr_small(n % p, r % p, p) % p
280
281
282def nCr_small(n: int, r: int, p: int) -> int:
283    """μž‘μ€ nCr mod p"""
284    if r > n:
285        return 0
286    if r == 0 or r == n:
287        return 1
288
289    num = den = 1
290    for i in range(r):
291        num = num * (n - i) % p
292        den = den * (i + 1) % p
293
294    return num * mod_pow(den, p - 2, p) % p
295
296
297# =============================================================================
298# 8. μ•½μˆ˜ (Divisors)
299# =============================================================================
300
301def divisors(n: int) -> List[int]:
302    """
303    n의 λͺ¨λ“  μ•½μˆ˜
304    μ‹œκ°„λ³΅μž‘λ„: O(√n)
305    """
306    result = []
307
308    for i in range(1, int(n ** 0.5) + 1):
309        if n % i == 0:
310            result.append(i)
311            if i != n // i:
312                result.append(n // i)
313
314    return sorted(result)
315
316
317def divisor_count(n: int) -> int:
318    """μ•½μˆ˜μ˜ 개수"""
319    factors = prime_factorization(n)
320    count = 1
321    for _, exp in factors:
322        count *= (exp + 1)
323    return count
324
325
326def divisor_sum(n: int) -> int:
327    """μ•½μˆ˜μ˜ ν•©"""
328    factors = prime_factorization(n)
329    total = 1
330    for p, e in factors:
331        total *= (pow(p, e + 1) - 1) // (p - 1)
332    return total
333
334
335# =============================================================================
336# 9. μ„ ν˜• λ””μ˜€νŒν† μŠ€ 방정식
337# =============================================================================
338
339def solve_linear_diophantine(a: int, b: int, c: int) -> Tuple[bool, int, int]:
340    """
341    ax + by = c의 μ •μˆ˜ν•΄ (x, y) μ°ΎκΈ°
342    λ°˜ν™˜: (ν•΄ 쑴재 μ—¬λΆ€, x, y)
343    """
344    g, x0, y0 = extended_gcd(abs(a), abs(b))
345
346    if c % g != 0:
347        return False, 0, 0
348
349    x0 *= c // g
350    y0 *= c // g
351
352    if a < 0:
353        x0 = -x0
354    if b < 0:
355        y0 = -y0
356
357    return True, x0, y0
358
359
360# =============================================================================
361# ν…ŒμŠ€νŠΈ
362# =============================================================================
363
364def main():
365    print("=" * 60)
366    print("μˆ˜ν•™κ³Ό μ •μˆ˜λ‘  (Number Theory) 예제")
367    print("=" * 60)
368
369    # 1. GCD / LCM
370    print("\n[1] GCD / LCM")
371    a, b = 48, 18
372    print(f"    gcd({a}, {b}) = {gcd(a, b)}")
373    print(f"    lcm({a}, {b}) = {lcm(a, b)}")
374    g, x, y = extended_gcd(a, b)
375    print(f"    ν™•μž₯ μœ ν΄λ¦¬λ“œ: {a}*{x} + {b}*{y} = {g}")
376
377    # 2. μ†Œμˆ˜
378    print("\n[2] μ†Œμˆ˜")
379    print(f"    17 is prime: {is_prime(17)}")
380    print(f"    18 is prime: {is_prime(18)}")
381    primes = sieve_of_eratosthenes(50)
382    print(f"    50 μ΄ν•˜ μ†Œμˆ˜: {primes}")
383    print(f"    60의 μ†ŒμΈμˆ˜λΆ„ν•΄: {prime_factorization(60)}")
384
385    # 3. λͺ¨λ“ˆλŸ¬ μ—°μ‚°
386    print("\n[3] λͺ¨λ“ˆλŸ¬ μ—°μ‚°")
387    mod = 1000000007
388    print(f"    2^10 mod {mod} = {mod_pow(2, 10, mod)}")
389    print(f"    3의 역원 mod 7 = {mod_inverse(3, 7)}")
390    print(f"    검증: 3 * {mod_inverse(3, 7)} mod 7 = {3 * mod_inverse(3, 7) % 7}")
391
392    # 4. μ‘°ν•©
393    print("\n[4] μ‘°ν•©λ‘ ")
394    comb = Combination(1000, mod)
395    print(f"    10C3 = {comb.nCr(10, 3)}")
396    print(f"    10P3 = {comb.nPr(10, 3)}")
397    print(f"    100C50 mod {mod} = {comb.nCr(100, 50)}")
398
399    # 5. 였일러 ν”Ό ν•¨μˆ˜
400    print("\n[5] 였일러 ν”Ό ν•¨μˆ˜")
401    for n in [10, 12, 7, 1]:
402        print(f"    Ο†({n}) = {euler_phi(n)}")
403
404    # 6. μ€‘κ΅­μΈμ˜ λ‚˜λ¨Έμ§€ 정리
405    print("\n[6] μ€‘κ΅­μΈμ˜ λ‚˜λ¨Έμ§€ 정리")
406    remainders = [2, 3, 2]
407    moduli = [3, 5, 7]
408    x = chinese_remainder_theorem(remainders, moduli)
409    print(f"    x ≑ 2 (mod 3), x ≑ 3 (mod 5), x ≑ 2 (mod 7)")
410    print(f"    x = {x}")
411    print(f"    검증: {x % 3}, {x % 5}, {x % 7}")
412
413    # 7. 루카슀 정리
414    print("\n[7] 루카슀 정리")
415    n, r, p = 1000, 500, 13
416    print(f"    C({n}, {r}) mod {p} = {lucas(n, r, p)}")
417
418    # 8. μ•½μˆ˜
419    print("\n[8] μ•½μˆ˜")
420    n = 36
421    print(f"    {n}의 μ•½μˆ˜: {divisors(n)}")
422    print(f"    μ•½μˆ˜ 개수: {divisor_count(n)}")
423    print(f"    μ•½μˆ˜ ν•©: {divisor_sum(n)}")
424
425    # 9. λ””μ˜€νŒν† μŠ€ 방정식
426    print("\n[9] μ„ ν˜• λ””μ˜€νŒν† μŠ€ 방정식")
427    a, b, c = 3, 5, 7
428    exists, x, y = solve_linear_diophantine(a, b, c)
429    print(f"    {a}x + {b}y = {c}")
430    print(f"    ν•΄ 쑴재: {exists}, x={x}, y={y}")
431    print(f"    검증: {a}*{x} + {b}*{y} = {a * x + b * y}")
432
433    print("\n" + "=" * 60)
434
435
436if __name__ == "__main__":
437    main()