guest@cp-base:~/home$

Number Theory

(6)

Number theory utilities and functions

$ls number-theory/|wc -l6 templates found
template_sieve.cpp

Sieve of Eratosthenes

[Number Theory]

Linear sieve computing primes, smallest prime factor (SPF), Euler's totient, and Mobius function in O(n).

#sieve#prime#number-theory+2
$ cat sieve
template_pollard-rho.cpp

Pollard's Rho Factorization

[Number Theory]

Factorize 64-bit integers into primes using Pollard's Rho with Miller-Rabin primality testing.

#factorization#pollard-rho#number-theory+1
$ cat pollard-rh..
template_number-theory-basics.cpp

Number Theory Basics

[Number Theory]

Primality test, factorization, Euler's totient, divisors, integer sqrt, and perfect power check.

#prime#factorization#totient+2
$ cat number-the..
template_modint.cpp

Modular Integer (ModInt)

[Number Theory]

Type-safe modular arithmetic with operator overloading for clean competitive programming code.

#modint#modular#arithmetic+1
$ cat modint
template_miller-rabin.cpp

Miller-Rabin Primality Test

[Number Theory]

Deterministic Miller-Rabin primality test for 64-bit integers using verified witness sets.

#primality-test#miller-rabin#deterministic+1
$ cat miller-rab..
template_matrix-exponentiation.cpp

Matrix Exponentiation

[Number Theory]

Binary exponentiation on square matrices for solving linear recurrences in O(n^3 log k).

#matrix#exponentiation#linear-recurrence+1
$ cat matrix-exp..