Category: Math

The recursion version is not slower than the while loop version when it is o2 optimized or above. See https://godbolt.org/z/E9jYefrKG.

If we have a * x = 1 (mod kMod), we call x is a multiplicative inverse of a when modular is kMod (in this post, kMod is a prime number). Usually we use a^-1 to represent it. Binary Exponentiation Given a and kMod, we can get a^-1 in O(logkMod) time. Dynamic Programming This solves…

The this post, we introduced how to get all prime numbers from 1 to n in o(nloglogn) time. Base on which, we can do prime factorization in O(logn) time.

Prime Numbers in [1, n] The naive method takes O(n^1.5)) time. We could use the famous Sieve of Eratosthenes algorithm.

Summary In this post, I will introduce some common techniques related to divisors and factors.  Details Number of Divisors GCD

Summary In this post, I will introduce some problems related to date.  Details Is Leap Year Days of the Year Days from 1900 Days Between Dates