Numbers

type(10**9), type(1e9)  # (<class 'int'>, <class 'float'>)
1e9 == 10**9  # True, but 1e9 is a float: use 10**9
int(" 42 "), int("1_000"), int("-7")  # (42, 1000, -7)
int("١٢٣")  # 123: any Unicode decimal digits parse
int(3.99), int(-3.99)  # (3, -3): truncates toward 0
True + True, isinstance(True, int)  # (2, True)
{1: "a", 1.0: "b", True: "c"}  # {1: 'c'}: one key

a, b = -7, 2
q, r = divmod(a, b)  # (-4, 1)
assert q * b + r == a  # always holds
 
# truncating division (C, Java, JS Math.trunc), exactly
def tdiv(a: int, b: int) -> int:
    q = abs(a) // abs(b)
    return q if (a < 0) == (b < 0) else -q
 
 
tdiv(-7, 2), int(-7 / 2)  # (-3, -3)
int(10**30 / 7) == 10**30 // 7  # False: / went via float

import sys
 
INT_MAX = 2**31 - 1
x = INT_MAX + 1  # 2147483648: no overflow
(x + 2**31) % 2**32 - 2**31  # -2147483648: wrapped
sys.maxsize + 1  # 9223372036854775808: still fine
 
sys.get_int_max_str_digits()  # 4300
try:
    str(7**6000)  # computing 7**6000 is fine; printing isn't
except ValueError as e:
    print(type(e).__name__)  # ValueError
len(hex(7**6000)), (7**6000).bit_length()  # (4214, 16845)
sys.set_int_max_str_digits(0)  # 0 = no limit
len(str(7**6000))  # 5071

MASK = 0xFFFFFFFF
x = -5
x & MASK  # 4294967291
format(x & MASK, "032b")[-8:]  # '11111011'
 
 
def to_signed32(u: int) -> int:
    u &= MASK
    return u - (1 << 32) if u & (1 << 31) else u
 
 
to_signed32(0xFFFFFFFF), to_signed32(2**31)
# (-1, -2147483648)
-7 >> 1, ~5, 6 & -6  # (-4, -6, 2): lowest set bit

import math
from fractions import Fraction
 
(0.1).as_integer_ratio()
# (3602879701896397, 36028797018963968)
Fraction("0.1") + Fraction("0.2") == Fraction("0.3")  # True
math.isclose(1e-10, 0, abs_tol=1e-9)  # True
10**16 / 3 == (10**16 + 1) / 3  # True: different, same float

import math
 
math.isqrt(10**30 + 1)  # 1000000000000000
n = 10**34 - 1
int(n**0.5), math.isqrt(n)
# (100000000000000000, 99999999999999999)
math.log2(2**50 - 1), (2**50 - 1).bit_length() - 1
# (50.0, 49): only bit_length is right
pow(38, -1, 97)  # 23, since 38 * 23 % 97 == 1
math.comb(52, 5)  # 2598960 poker hands

MOD = 10**9 + 7
(3 - 5) % MOD  # 1000000005: non-negative already
pow(2, 10**18, MOD)  # 719476260, instantly
inv3 = pow(3, -1, MOD)
6 * inv3 % MOD  # 2: "6 / 3" mod p
pow(3, MOD - 2, MOD) == inv3  # True: Fermat

n = 9045
[int(d) for d in str(n)]  # [9, 0, 4, 5]
sum(map(int, str(n)))  # 18
 
digits: list[int] = []
m = n
while m:
    m, d = divmod(m, 10)
    digits.append(d)  # least significant first
print(digits)  # [5, 4, 0, 9]
int("".join(map(str, [9, 0, 4, 5])))  # 9045

import sys
 
sys.int_info.bits_per_digit  # 30
sys.getsizeof(1), sys.getsizeof(2**30)  # (28, 32)
sys.getsizeof(10**100)  # 72: 12 digits of 30 bits

import math
from math import gcd
 
rows, cols = 3, 4
r, c = divmod(7, cols)  # (1, 3): cell of index 7
r * cols + c  # 7: and back
 
n = 36
divisors = sorted(
    d
    for i in range(1, math.isqrt(n) + 1)
    if n % i == 0
    for d in {i, n // i}
)
print(divisors)  # [1, 2, 3, 4, 6, 9, 12, 18, 36]
 
dx, dy = -4, 6
g = gcd(dx, dy)  # 2: gcd is never negative
key = (dx // g, dy // g)  # (-2, 3)
if key[0] < 0:  # one sign convention per slope
    key = (-key[0], -key[1])
print(key)  # (2, -3)
 
-(-7 // 2), 8 & 7 == 0, (-3) % 2  # (4, True, 1)

import math
 
 
def primes_upto(n: int) -> list[int]:
    if n < 2:
        return []
    is_p = bytearray([1]) * (n + 1)  # 1 byte per number
    is_p[0] = is_p[1] = 0
    for p in range(2, math.isqrt(n) + 1):
        if is_p[p]:  # cross off p*p, p*p + p, ...
            hits = range(p * p, n + 1, p)
            is_p[p * p :: p] = bytes(len(hits))
    return [i for i, flag in enumerate(is_p) if flag]
 
 
print(primes_upto(30))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
print(len(primes_upto(10**6)))  # 78498

def factorize(n: int) -> dict[int, int]:
    factors: dict[int, int] = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors[d] = factors.get(d, 0) + 1
            n //= d
        d += 1 if d == 2 else 2  # 2, then odd numbers
    if n > 1:  # what is left is prime
        factors[n] = factors.get(n, 0) + 1
    return factors
 
 
f = factorize(360)
print(f)  # {2: 3, 3: 2, 5: 1}
count = 1
for e in f.values():
    count *= e + 1
print(count)  # 24 divisors

MOD = 10**9 + 7
N = 10**5
 
fact = [1] * (N + 1)
for i in range(1, N + 1):
    fact[i] = fact[i - 1] * i % MOD
inv_fact = [1] * (N + 1)
inv_fact[N] = pow(fact[N], -1, MOD)  # one inverse
for i in range(N, 0, -1):  # the rest by stepping down
    inv_fact[i - 1] = inv_fact[i] * i % MOD
 
 
def ncr(n: int, r: int) -> int:
    if not 0 <= r <= n:
        return 0
    top = fact[n] * inv_fact[r] % MOD
    return top * inv_fact[n - r] % MOD
 
 
print(ncr(5, 2), ncr(10**5, 5 * 10**4))  # 10 149033233

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyz"
 
 
def to_base(n: int, base: int) -> str:
    if not 2 <= base <= 36:
        raise ValueError("base must be in 2..36")
    if n == 0:
        return "0"
    sign = "-" if n < 0 else ""
    n = abs(n)
    out: list[str] = []
    while n:
        n, r = divmod(n, base)
        out.append(ALPHABET[r])
    return sign + "".join(reversed(out))
 
 
print(to_base(100, 7), to_base(-10, 2))  # 202 -1010
print(int(to_base(123456789, 36), 36))  # 123456789

INT_MIN, INT_MAX = -(2**31), 2**31 - 1
 
 
def reverse_int(x: int) -> int:
    n, r = abs(x), 0  # abs first: -123 % 10 == 7
    while n:
        n, d = divmod(n, 10)
        r = r * 10 + d
    r = -r if x < 0 else r
    return r if INT_MIN <= r <= INT_MAX else 0
 
 
print(reverse_int(-123), reverse_int(120))  # -321 21
print(reverse_int(1534236469))  # 0: 9646324351 overflows

from collections import Counter
from math import gcd
 
 
def direction(dx: int, dy: int) -> tuple[int, int]:
    g = gcd(dx, dy)  # > 0 unless both are 0
    dx, dy = dx // g, dy // g
    if dx < 0 or (dx == 0 and dy < 0):
        dx, dy = -dx, -dy  # one sign per direction
    return dx, dy
 
 
def max_points(pts: list[tuple[int, int]]) -> int:
    best = min(len(pts), 1)
    for i, (x1, y1) in enumerate(pts):
        dirs = Counter(
            direction(x2 - x1, y2 - y1)
            for x2, y2 in pts[i + 1 :]
        )
        best = max(best, 1 + max(dirs.values(), default=0))
    return best
 
 
pts = [(1, 1), (3, 2), (5, 3), (4, 1), (2, 3), (1, 4)]
print(max_points(pts))  # 4

type Mat = tuple[int, int, int, int]  # [[a, b], [c, d]]
 
 
def mat_mul(x: Mat, y: Mat, m: int) -> Mat:
    a, b, c, d = x
    e, f, g, h = y
    return (
        (a * e + b * g) % m,
        (a * f + b * h) % m,
        (c * e + d * g) % m,
        (c * f + d * h) % m,
    )
 
 
def fib(n: int, m: int = 10**9 + 7) -> int:
    result: Mat = (1, 0, 0, 1)  # identity
    base: Mat = (1, 1, 1, 0)
    while n:  # square-and-multiply, like pow
        if n & 1:
            result = mat_mul(result, base, m)
        base = mat_mul(base, base, m)
        n >>= 1
    return result[1]  # base**n = [[F(n+1), F(n)], ...]
 
 
print([fib(i) for i in range(10)])
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
print(fib(10**18))  # 209783453