---

here the conventional process will fail when input is very large (i.e: N=2000000 & M=0)
so some tricks are used here. factors divisible by 5 or 2 ignore first.
i.e: 5*2*3=30 that means a pair of 2&5 produce trailing zero.
Henece all 2 or 5 facotrs are ignored. then I multiply the extra 5 or 2.
i.e:let there is two 5 & three 2. so here is two pairs of 2 & 5 and one extra 2.
Another tricks is applied: only last digit is enough in successive   multiplication
to determine the last digit of final result.
i.e: 6*7*3=126. the last digist is 6. we can get the same result as follows:
1st step: 6*7=42(last digit is 2. now we will consider 42 as 2)
2nd step: 2*3=6
Thus this gives the same result. It is true for all cases.
this tricks is must for large input.
i.e: (i.e: N=2000000 & M=0)
in convention approach you may think as follows:
1st step: 2000000*199999*199998*…….2*1
2nd step: find out the last digit of the above multiplication result.
But there is no such big variable to store such large multiplication result.

#include<stdio.h>
int main()
{
    int m,n,t,f,i,k,result,factorNotdivisibleBy5or2;
    while(scanf("%d%d",&n,&m)==2)
    {
        t=0;
        f=0;
        result=1;
        for(i=n; i>n-m; i--)
        {
            factorNotdivisibleBy5or2=i;
            while(!(factorNotdivisibleBy5or2&1))
            {
                factorNotdivisibleBy5or2>>=1;
                t++;
            }
            while(factorNotdivisibleBy5or2%5==0)
            {
                factorNotdivisibleBy5or2/=5;
                f++;
            }
            result=(result*factorNotdivisibleBy5or2)%10;
        }
        for(i=t; i<f; i++)
        {
            result=(result*5)%10;
        }
        for(i=f; i<t; i++)
        {
            result=(result*2)%10;
        }
 
        printf("%d\n",result%10);
    }
    return 0;
}

 

---

Next Previous