"""
Exact arithmetic helpers for math competitions.
This module is designed to be copy-pasted into Jupyter notebooks.
No external dependencies beyond standard library + sympy.
"""
from fractions import Fraction
from functools import reduce
from math import gcd, factorial
import operator
# Try to import sympy, but work without it for basic operations
try:
from sympy import (
symbols, Eq, solve, simplify, factor, expand,
Rational, Integer, mod_inverse, Matrix, sqrt, Abs,
binomial, factorial as sym_factorial, floor, ceiling,
isprime, factorint, divisors, totient, mobius
)
from sympy.parsing.sympy_parser import parse_expr
SYMPY_AVAILABLE = True
except ImportError:
SYMPY_AVAILABLE = False
# =============================================================================
# BASIC EXACT ARITHMETIC (no sympy needed)
# =============================================================================
def frac(n, d=1):
"""Create an exact fraction."""
return Fraction(n, d)
def exact_sum(values):
"""Sum values exactly using Fraction arithmetic."""
return sum(Fraction(v) if not isinstance(v, Fraction) else v for v in values)
def exact_product(values):
"""Multiply values exactly."""
result = Fraction(1)
for v in values:
result *= Fraction(v) if not isinstance(v, Fraction) else v
return result
def lcm(a, b):
"""Least common multiple."""
return abs(a * b) // gcd(a, b)
def lcm_many(values):
"""LCM of multiple values."""
return reduce(lcm, values)
def gcd_many(values):
"""GCD of multiple values."""
return reduce(gcd, values)
def mod_exp(base, exp, mod):
"""Modular exponentiation: (base^exp) % mod, exact."""
result = 1
base = base % mod
while exp > 0:
if exp % 2 == 1:
result = (result * base) % mod
exp = exp >> 1
base = (base * base) % mod
return result
def mod_inv(a, m):
"""Modular inverse of a mod m using extended Euclidean algorithm."""
def extended_gcd(a, b):
if a == 0:
return b, 0, 1
gcd_val, x1, y1 = extended_gcd(b % a, a)
x = y1 - (b // a) * x1
y = x1
return gcd_val, x, y
g, x, _ = extended_gcd(a % m, m)
if g != 1:
raise ValueError(f"No modular inverse: gcd({a}, {m}) = {g}")
return (x % m + m) % m
def crt(residues, moduli):
"""
Chinese Remainder Theorem.
Find x such that x ≡ residues[i] (mod moduli[i]) for all i.
"""
if len(residues) != len(moduli):
raise ValueError("residues and moduli must have same length")
M = 1
for m in moduli:
M *= m
x = 0
for a_i, m_i in zip(residues, moduli):
M_i = M // m_i
inv = mod_inv(M_i, m_i)
x = (x + a_i * M_i * inv) % M
return x
def comb(n, k):
"""Exact binomial coefficient C(n, k)."""
if k < 0 or k > n:
return 0
if k == 0 or k == n:
return 1
k = min(k, n - k)
result = 1
for i in range(k):
result = result * (n - i) // (i + 1)
return result
def perm(n, k):
"""Exact permutation P(n, k) = n! / (n-k)!"""
if k < 0 or k > n:
return 0
result = 1
for i in range(k):
result *= (n - i)
return result
# =============================================================================
# SYMPY-BASED EXACT ARITHMETIC
# =============================================================================
def exact_eval(expr_str, exact=True):
"""
Evaluate a mathematical expression with exact arithmetic.
Args:
expr_str: String expression like "1/3 + 1/4" or "sqrt(2) * 3"
exact: If True, return exact form; if False, return float
Returns:
Exact result (Fraction, int, or sympy expression)
"""
if not SYMPY_AVAILABLE:
# Fallback: try to evaluate as Python with Fraction
try:
# Replace / with Fraction division
safe_expr = expr_str.replace('/', '/Fraction(1)*Fraction(1)/')
return eval(expr_str, {"Fraction": Fraction, "__builtins__": {}})
except:
raise ImportError("sympy required for this expression")
expr = parse_expr(expr_str, evaluate=True)
expr = simplify(expr)
if not exact:
return float(expr.evalf())
# Try to return as Python int or Fraction
if expr.is_Integer:
return int(expr)
if expr.is_Rational:
return Fraction(int(expr.p), int(expr.q))
# Return sympy expression for irrationals
return expr
def exact_solve(equation_str, var='x'):
"""
Solve an equation exactly.
Args:
equation_str: Equation like "x^2 - 4 = 0" or expression (assumed = 0)
var: Variable name to solve for
Returns:
List of exact solutions
"""
if not SYMPY_AVAILABLE:
raise ImportError("sympy required for solving equations")
x = symbols(var)
if '=' in equation_str:
lhs, rhs = equation_str.split('=')
expr = parse_expr(lhs) - parse_expr(rhs)
else:
expr = parse_expr(equation_str)
solutions = solve(Eq(expr, 0), x)
# Convert to Python types where possible
result = []
for sol in solutions:
if sol.is_Integer:
result.append(int(sol))
elif sol.is_Rational:
result.append(Fraction(int(sol.p), int(sol.q)))
else:
result.append(sol)
return result
def exact_simplify(expr_str):
"""Simplify an expression, returning exact form."""
if not SYMPY_AVAILABLE:
raise ImportError("sympy required")
expr = parse_expr(expr_str, evaluate=False)
return simplify(expr)
def exact_factor(expr_str):
"""Factor an expression."""
if not SYMPY_AVAILABLE:
raise ImportError("sympy required")
expr = parse_expr(expr_str)
return factor(expr)
# =============================================================================
# NUMBER THEORY HELPERS
# =============================================================================
def prime_factors(n):
"""Return prime factorization as dict {prime: exponent}."""
if SYMPY_AVAILABLE:
return dict(factorint(n))
# Fallback implementation
factors = {}
d = 2
while d * d <= n:
while n % d == 0:
factors[d] = factors.get(d, 0) + 1
n //= d
d += 1
if n > 1:
factors[n] = factors.get(n, 0) + 1
return factors
def all_divisors(n):
"""Return all divisors of n."""
if SYMPY_AVAILABLE:
return list(divisors(n))
# Fallback
divs = []
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
divs.append(i)
if i != n // i:
divs.append(n // i)
return sorted(divs)
def euler_phi(n):
"""Euler's totient function."""
if SYMPY_AVAILABLE:
return totient(n)
# Fallback
result = n
p = 2
while p * p <= n:
if n % p == 0:
while n % p == 0:
n //= p
result -= result // p
p += 1
if n > 1:
result -= result // n
return result
# =============================================================================
# CONVENIENCE FOR COMPETITION OUTPUT
# =============================================================================
def format_answer(value, fmt='int'):
"""
Format answer for competition submission.
Args:
value: The computed answer
fmt: 'int' (integer), 'frac' (a/b), 'mod' (integer mod), 'decimal' (float)
Returns:
String ready for submission
"""
if fmt == 'int':
if isinstance(value, Fraction):
if value.denominator != 1:
raise ValueError(f"Expected integer, got {value}")
return str(value.numerator)
return str(int(value))
elif fmt == 'frac':
if isinstance(value, Fraction):
if value.denominator == 1:
return str(value.numerator)
return f"{value.numerator}/{value.denominator}"
return str(value)
elif fmt == 'mod':
return str(int(value))
elif fmt == 'decimal':
return str(float(value))
else:
return str(value)
