Some of the Most Used Algorithms

/*
 * Title : Some of the Most Used Algorithms
 * Language : C / C++
 * Author: Sharif Bin Haque, Dhaka, Bangladesh
*/

//requires bool arr[] for storing primality (0= prime, 1= composite)
void SieveOfEratosthenes (int n)
{
    arr[0]=arr[1]=1;
    int i,j;
    for (i=2;i<=n;i++) if (arr[i]==0) for (j=2;i*j<=n;j++) arr[i*j]=1;
}

// arr[0<=i<=n] is predefined to be equal i
void EulerPhi (ll n)
{
    long long i,j;
    for (i=2;i<=n;i++) if (arr[i]==i) for (j=1;i*j<=n;j++) arr[i*j]-=arr[i*j]/i;
}

#define ll long long
ll BigMOD (ll base, ll pow, ll mod)
{
    ll ans=1;
    while (pow>0)
    {
        if (pow%2==1) ans=ans%mod * base%mod, pow--;
        else while (pow%2==0)base=((base%mod)*(base%mod))%mod, pow/=2;
    }
    return ans % mod;
}

// vector<ll> fact stores factorial value of 0<=i<=n
ll Fast_nCr (ll n, ll r)
{
    if (n==0 || r==0) return 1;
    else if (r>n) return 0;
    return (fact[n]*BigMOD(fact[r],M-2,M)*BigMOD(fact[n-r],M-2,M))%M;
}

ll Lucas_nCr( ll a, ll b)
{
    if (a==0 || b==0) return 1;
    else if (b>a) return 0;
    ll ai=a%M, bi=b%M;
    return (Fast_nCr(ai,bi)*(Lucas_nCr(a/M,b/M))%M);
}

// The Following code is from GeekforGeeks
long long FastPower(long long base, long long power) {
    long long result = 1;
    while(power > 0) {
        if(power % 2 == 1) { // Can also use (power & 1) to make code even faster
            result = (result*base) ;
        }
        base = (base * base);
        power = power / 2; // Can also use power >>= 1; to make code even faster
    }
    return result;
}