Math facts

Segmented Sieve

Use When we have to generate large number of prime Numbers Click Here

BitHacks

Number of bits required to represent a number: $\lfloor {\log_2{n}} \rfloor + 1$

For More Bit Tricks:Click Here

Useful nCr Technique

Divide by their GCD’s to prevent overflow

For fast Calculation:

ll NcR(ll n, ll r) 
{  
    ll p = 1, k = 1;  
    if (n - r < r) 
        r = n - r; 

    if (r != 0) { 
        while (r) { 
            p *= n; 
            k *= r; 
            ll m = __gcd(p, k); 
            p /= m; 
            k /= m; 
            n--; 
            r--; 
        } 
    } 

    else
        p = 1; 

    return p;
}

Cool Geometry Properties

Find Area of triangle using Side length Heron’s Formula.

$\Delta = \sqrt{P*(P-A)*(P-B)*(P-C)}; P = \frac{A+B+C}{2}$

Cool Mod properties

(a+b) % m = (a % m+b % m) % m
(a-b) % m = (a % m−b % m) % m
(a*b) % m = (a % m*b % m) % m

Comparing Double values

if(abs(a-b)<1e-9)
{
	cout<<"a and b are equal";
}

GCD Properties

gcd(a,b)=gcd(a,b%a) Let X=gcd(a,b) then gcd(X/a,X/b)=1

Find divisors of a number

for (int i = 2; i * 1ll * i <= x; ++i) {
    if (x % i == 0) {
        dd.push_back(i);
        if (i != x / i) {
            dd.push_back(x / i);
        }
    }
}

Goldbachs Conjecture

It says any number can be expressed as a sum of 2 prime numbers.

Cool Problems

When asked how to make two numbers equal by series of divisions Represent those numbers in terms of powers of those numbers.

          for eg allowed operations are /2,/3,/5 then
          A=x*2^a * 3^b * 5^c
          B=y*2^a2 * 3^b2 * 5^c2
          if x is same as y it can be made equal</p>

Rajagopalan Gangadharan