Modular inverse

For Questions involving big numbers, where you have to print the numbers mod a prime number(such as 1000000007), the following function would come-in handy:





// the function calculated (inverse of a) mod b
LL mul_inv(LL a, LL b)
{
    LL b0 = b, t, q;
    LL x0 = 0, x1 = 1;
    if (b == 1) return 1;
    while (a > 1) {
        q = a / b;
        t = b, b = a % b, a = t;
        t = x0, x0 = x1 - q * x0, x1 = t;
    }
    if (x1 < 0) x1 += b0;
    return x1;
}

GCD / HCF

The following is a simple yet efficient recursive code to calculate the GCD of 2 numbers.


Euler Method


#define LL long long int
LL gcd(LL a, LL b)
{
if(a==0)return b;
else return gcd(b%a,a);
}

Fast I/O in C++

Most of the competitions require non negative numbers.

The following code works perfectly well for them 

#define LL long long int 

#define gc getchar_unlocked()  

inline void inp(LL &x) 

{
    register LL c = gc ;
    x = 0;
    for(; ((c<48 || c>57)); c = gc );
    for(; c>47 && c<58 ; c = gc )x = (x<<1) + (x<<3) + c - 48;
}

However, if negative numbers are also allowed, 

#define LL long long int 
#define gc getchar_unlocked()   

inline void inp(LL &x)

 {
    register LL c = gc , neg=0;
    x = 0;
    for(; ((c<48 || c>57) && c != '-'); c = gc );
    if(c=='-') {neg = 1;c = gc();}
    for(; c>47 && c<58 ; c = gc )x = (x<<1) + (x<<3) + c - 48;
    if(neg)x = -x;
} 

Note: Define your variable as "long long int" otherwise, this will show an error. 

For strings,

#define gc getchr_unlocked();

inline void inpl(char *str)
{
    register char c = 0;
    register int i = 0;
    while (c < 33)c = gc ;
    while (c != '\n') {
        str[i] = c;
        c = gc ;
        i = i + 1;
    }
    str[i] = '\0';
}