long long ans=1;
for(int i=1; i<=20000000; i++)
{
ans*=i;
while(ans%10==0)
ans/=10;
ans%=100000000000LL;
}
cout<<ans%10<<endl;
####
This is a code of finding the last-non-zero-digit of factorial(20000000) my question why & how 10^11 is safe as modulo in this case? shouldn't it be at least 10^15? since 19999998 * 19999999 = 399999940000002 which is greater than 10^11. please clear it to me. Thanks in advance.
It shouldn't. In fact with modulo 10^15 it won't work. Modulo 10^15 means that ans can be about 10^15 before multiplication and you multiply it by number about 10^7. It's 10^22, which is much more than long long max value. When you use modulo 10^11, ans is always less than 2 * 10^18 and it fits long long.
will 10^8 work safely? how to calculate which MINIMUM mod will work safely?
I think even just 10 will work. Because you need only last digit, so you can keep only it
No it doesn't.
Such an approach will e.g. fail for 15!, because 14! = 87178291200 and 87178291200 * 15 = 1307674368000. If you only keep the last digit, you'd in this case answer 3 and not 8.
A more illustrative example to look at might be the product 3*4*5, the last digit after removing trailing 0s is 6, but if you mod by 10 after 3*4 you'll answer 1.
The reason why only keeping the last digit fails is because factors of 5 (and 2) might cause our current last digit to "jump up to the second last digit". Let's look at 3*4*5 again. 3*4 = 12 and at this point we don't really care about the 1 in 12, but look what happens when we multiply by 5:
3 * 4 * 5 = 12 * 5 = (10 + 2) * 5 = 50 + 10 = 60
Did you see what happened? Our last digit 2 became a 10, but our second last digit just went from 10 to 50, so all of a sudden the second last digit was in fact very important!
Will then mod 100 suffice? No because we can have a "jump up until the third last digit". How many "jump ups" can we have? Well as said in the comment below, the biggest number of factors of 5 in a number we will multiply with (provided we have as many factors of 2 in the accumulated product).