PROGRAMMAR's blog

By PROGRAMMAR, history, 7 years ago, In English

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.

  • Vote: I like it
  • -18
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    will 10^8 work safely? how to calculate which MINIMUM mod will work safely?

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think even just 10 will work. Because you need only last digit, so you can keep only it

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like 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).