I will try to explain the working of the fast multiplication function in brief.If we want to do an operation like 10^18 * 10^18 % MOD, where MOD is also of the order of 10^18, direct multiplication will result in overflow of even unsigned long long. This was the reason for many people getting WA for MTRICK in January 14 Long.

The best way to solve this is to split the multiplication operation into different steps so that the modulo operator can be applied in intermediate steps to avoid overflow.The idea for this is similar to the concept used in fast exponentiation. We can write a * b as 2 * ( a * (b/2) ). Again we write a * (b/2) as 2 * (a * (b/4)). This is the recursion we used to calculate the value of a * b. As we are dividing b by 2 at each step , we can get the answer in logarithmic time i.e. log(b).

Now if we want to multiply a by b and b is say 13, then a * b = a * 13 can be written

```
a * 13 = a + 2 * ( 13/2 * a)
= a + 2 * ( 6 * a)
= a + 2 * ( 2 * (6/2 * a))
= a + 2 * (2 * (3 * a))
= a + 2 * (2 * (2 * (a + (3/2 * a))))
= a + 2 * (2 * (2 * (a + ( 1 * a))))
```

This splitting can easily be done by recursion.

The main advantage of splitting is that we can take modulo in the intermediate steps which is not possible in direct multiplication. Note: b>>1 gives the quotient obtained when b is divided by 2.

Now consider the code:

```
long long multiple(long long a, long long b, long long c) // a * b % c
{
if (b == 0) { //Base case a * 0 =0
return 0
}
long long ret = multiple(a, b >> 1, c) //Multiply a by (b>>1).
ret = (ret + ret) % c //we double the value of ret i. 2 * (a * (b>>1)). Take MOD in this step
if (b & 1) { //implies b is ODD
ret = (ret + a) % c //if b is odd then we express it as a * b = a+ a * (b>>1). We have computed a*(b>>1) in the previous step by recursion i.e the value ret. We now add the extra a to it.
}
return ret
```

}

Hope the explanation is clear. Please feel free to ask anything if you have doubts.

(P.S. There is another shorter alternative but it is pretty difficult to understand. You can refer to the link given by @iscsi below in the comments)