Common Formulae — Legendre's Formula & Divisor Convolutions
Legendre’s formula, divisor and multiple convolutions in O(n log n), offline-difference batch processing for H(n)=Σf(d)g(⌊n/d⌋).
Tags
#Legendre
2 posts
Tags
2 posts
Legendre’s formula, divisor and multiple convolutions in O(n log n), offline-difference batch processing for H(n)=Σf(d)g(⌊n/d⌋).
GCD/LCM properties, Bézout/Frobenius, Euler’s theorem with power-tower reduction and φ-chain technique, congruence system merging via exGCD, CRT, and n! prime factorisation via Legendre’s formula.