Last non-zero digit in huge fatorial numbers.

Блог пользователя aajjbb

Автор aajjbb, 12 лет назад, По-английски

Hi, I have the following problem, given a number N between 1 and 1000000, print their last non-zero digit from N!.

The only strategy I've got was try to store the last digits of their fatorial, but this strategy fails when the number N reaches '25'. There's an efficient solution ? since the time limit is strict.

This is my actual strategy, storing in mem[i] the last digit of i!:

    ll fat = 1, last = 1;
    for(int i = 1; i <= 1000010; i++) {
        if(i % 5 == 0 || last % 5 == 0) {
            ll tmp = last * i;
            while(tmp % 10 == 0) tmp /= 10;
            last = tmp % 10;
        } else {
            last = (last * i) % 10;
        }
        mem[i] = last;
    }

algorihm, number theory, big numbers

aajjbb
12 лет назад
10

Комментарии (9)

Показать архивные | Написать комментарий?

riadwaw

12 лет назад, # |

← Rev. 5 →

Just calculate it without degrees of 2 and 5, because only 2 * 5 gives us 0
+Calculate additional degree of 2

int last = 1, d2 = 0;
for(int i=1;i<=N;++i){
  int ii = i;
  while(ii%2==0){
  d2++;
  ii/=2;
  }
  while(ii%5==0){
  d2--;
  ii/=5;
  }
  last = (last * ii) % 10;
}

for(int i = 0;i < d2 ;++i){
  last = (last * 2)%10;
}

Here last is the last digit of N!

→ Ответить

aajjbb

12 лет назад, # ^ |

but this multiplicative property with 2 is cumulative ? to find the last digit for a range of numbers, is possible ? being mem[i] the number of the last digit for i! ? sorry for my poor math skills.

int last = 1, d2 = 0;
    for(i = 1; i <= 1000010; ++i) {
        int ii = i;
        while(ii % 2 == 0) {
            d2++;
            ii/=2;
        }
        while(ii % 5 == 0) {
            d2--;
            ii/=5;
        }
        last = (last * ii) % 10;
        for(j = 0; j < d2 ; ++j) {
            last = (last * 2)%10;
        }
        mem[i] = last;

→ Ответить

riadwaw

12 лет назад, # ^ |

you may calc d2[i] and last[i] just as in my example (starting with copy previous one), after that you may calc mem[i]

→ Ответить

aajjbb

12 лет назад, # ^ |

I'm memorizing d2[i], mem[i]. is this way, but it's now slowly, I've tried some optimizations on (*2) degrees but didn't worked.

  mem[1] = 1; d2[1] = 0;
    for(i = 2; i <= 1000010; ++i) {
        mem[i] = mem[i - 1];
        d2[i] = d2[i - 1];
        int ii = i;
        while(ii % 2 == 0) {
            d2[i]++;
            ii/=2;
        }
        while(ii % 5 == 0) {
            d2[i]--;
            ii/=5;
        }
        mem[i] = (mem[i] * ii) % 10;
        for(j = 0; j < d2[i] - d2[i - 1]; j++) {
            mem[i] = (mem[i]*2) % 10;
        }
    }

→ Ответить

Proscriptus

12 лет назад, # |

Since N<=1000000 I think it's the easiest way to solve the problem. It just works.

int lastDigit(int n)
{
	long long ans(1);
	for (int i=1; i<=n; ++i)
	{
		ans*=i;
		while (ans%10==0)
			ans/=10;
		ans%=1000000000;
	}
	return ans%10;
}

→ Ответить

aajjbb

12 лет назад, # ^ |

I have a strict time limit, so this solutions get TLE. I think AlexDmitriev solution is the best one, but I'm doubt on how to memorize the last digits take as example his solutions which find each number a time.

→ Ответить

Proscriptus

12 лет назад, # |

← Rev. 3 →

O(logN) solution. Calculating n!/(2^max2*5^max5) modulo 2 and modulo 5 (max2 and max5 are degrees of 2 and 5 in n! respectively). After that using chinese remainder theorem to find n!/(2^max2*5^max5) modulo 10. The last step is to print the answer multiplied by 2^(max2-max5). http://pastebin.com/R6uXeWY6

→ Ответить

aajjbb

12 лет назад, # ^ |

What an amazing solution, thank you, I didn't knew about Chinese remainder theorem.. I didn't got the recursion in 'mod5' function yet, but looks clever, also the 'if' with (n&1) is new to me also, for what it stands about ? again, thank you.

→ Ответить

Proscriptus

12 лет назад, # ^ |

You can read about mod5 here. n&1 checks whether the last bit of n is equal to 1. So it's equivalent to n%2. About bitwise operations you can read more on wiki.

→ Ответить