Matematik & Sayı Teorisi

Nasıl düşünülür

Sayı teorisi problemleri aritmetiği modül altında güvenli tutup çarpımsal yapıyı sömürme becerini sınar. İki alışkanlık çok önemlidir: (1) her çarpmadan sonra % m al ki ara çarpımlar taşmasın; (2) modüler üs alma (ikili üs alma: square-and-multiply) ile a^b mod m’yi O(log b)’de hesapla, asla naif pow çağırma.

Asallar için Eratosthenes kalburu varsayılan: n+1 boyutunda boolean dizi, her asalın katlarını p*p’den başlayarak çiz. GCD için Öklid algoritması tek satırdır: gcd(a, b) = b === 0 ? a : gcd(b, a % b). LCM a / gcd(a, b) * b’dir (önce böl, taşmayı önle). n choose k mod m için faktöriyeller ve ters faktöriyeller mod m önhazırla (m asalsa Fermat).

Şablon şekilleri

Şekil	Temel hamle	Örnek
Modüler üs	Square-and-multiply, her adımda mod	LC 50, LC 372
Kalbur	Boolean dizi, p*p’den çiz	LC 204
GCD / LCM	Öklid: gcd(b, a % b)	LC 1071, LC 365
Faktöriyel / bölünebilirlik	Sıfır sayımı, faktör sayma, kombinatorik mod m	LC 172

Karmaşıklık temeli

Modüler üs: O(log b). Kalbur: O(n log log n). GCD: O(log min(a, b)). Önhazırlanan faktöriyeller: O(n) kurulum, sorgu başına O(1).

Şablondan probleme

1. İşlemi tanımla: üs, asal testi, GCD veya kombinatorik.
2. Modülü belirle, asal mı (Fermat geçerli)? Büyük mü?
3. Overflow önlemek için her adımda % m al.
4. Yalnızca problem birçok sorguyu amorti ediyorsa (faktöriyeller, kalbur) önhazırla.

/** Math template: modular exponentiation + GCD via Euclid. */

export function modPow(base: number, exp: number, mod: number): number {
  let result = 1n;
  let b = BigInt(base) % BigInt(mod);
  const m = BigInt(mod);
  let e = BigInt(exp);
  while (e > 0n) {
    if (e & 1n) result = (result * b) % m;
    b = (b * b) % m;
    e >>= 1n;
  }
  return Number(result);
}

export function gcd(a: number, b: number): number {
  a = Math.abs(a); b = Math.abs(b);
  while (b) { [a, b] = [b, a % b]; }
  return a;
}

export function lcm(a: number, b: number): number {
  if (a === 0 || b === 0) return 0;
  return Math.abs(a) / gcd(a, b) * Math.abs(b);
}

/** Math template: modular exponentiation + GCD via Euclid. */

export function modPow(base: number, exp: number, mod: number): number {
  let result = 1n;
  let b = BigInt(base) % BigInt(mod);
  const m = BigInt(mod);
  let e = BigInt(exp);
  while (e > 0n) {
    if (e & 1n) result = (result * b) % m;
    b = (b * b) % m;
    e >>= 1n;
  }
  return Number(result);
}

export function gcd(a: number, b: number): number {
  a = Math.abs(a); b = Math.abs(b);
  while (b) { [a, b] = [b, a % b]; }
  return a;
}

export function lcm(a: number, b: number): number {
  if (a === 0 || b === 0) return 0;
  return Math.abs(a) / gcd(a, b) * Math.abs(b);
}