- gcd(p,q)=gcd(p,p-q)
- Two integers a,b (b != 0) there exist two unique integers q and r such that a = bq + r, 0 <= r < b
- Bezout's identity states that if d = gcd(a,b) then there always exist integers x and y such that ax+by = d.
- number of primes smaller than n are n/log2(n)
- number of Divisors of a number n at max (n)^(1/3)
- number of prime Divisors of n at max log(n)
- harmonic series N + N/2 + N/3 + ... + 1 = O(N log N)
- (1+1/4 + 1/9 + 1/16 + 1/25 + ...) = (π^2 / 6)
- nCr = (n-1)C(r-1) + (n-1)Cr
- The total number of pairs (x,y) with 1≤x,y≤n,gcd(x,y)=1 is φ(1)+φ(2)+⋯+φ(n) , where φ is Euler's totient function.
- The number of divisors of a number n is (1+p1)*(1+p2)... where p1,p2..are the power of the prime factor of n that is n=a1^p1*a2^p2...
- N + N / 2 + N / 4 + N / 8 + N / 16 + ... is 2*N so it's O(N)
- Distinct values of the floor of (N / i) is 2 * sqrt(N) for i 1 to N.Proof
- There exists a k that n<=2^k<=2*n. Use in case we want to extend an array in the power of 2 still the Tc will be O(n)
- 1/1 +1/2 +1/3 ... 1/i.. =log(n) . i from 1 to n where n tends to inf
- set of bitwise AND of all subarray of an array such what ai<=n contain at max log(n) elements.
- A^B=C then A^C=B
More Statements are highly welcome.
Modular Arithmetics :
(a+b)%m = (a%m+b%m)%m
(a×b)%m = (a%m×b%m)%m
(a-b)%m = (a%m-b%m+m)%m [if a<b then adding m will ensure positive ans]
(a/b)%m = (axb−1)%m [modulo inv] also b,m are co-prime
Misc:
position of set MSB : bit = 31−__builtin_clz(number)
position of set LSB : bit = __builtin_ctz(number)
next power of 2 greater than n : ans = 1<<(32−__builtin_clz(number−1))
aww, i love number theory [QwQ]
note that the harmonic series are quite useful in proving the time-complexity of some problems.
set of gcd of all prefixes of an array such that ai<=n contain at max log(n) elements.