팩토리얼 끝자리 수 찾기

만약 다음과 같은 문제가 주어진다고 생각해보자.

b! / a! 이 주어질 때, 이 값의 끝자리 수는 무엇일까?

예를 들어 11! / 4!은 11 * 10 * 9 * 8 * 7 * 6 * 5 = 1,663,200 이기에 끝자리는 0이다.

13! / 10!의 경우에는 13 * 12 * 11 = 1,716 이기에 끝자리는 6이다.

막상 처음 보면 재미있는 문제가 아닐 수 없다.

이전에는 

팩토리얼 0의 개수 :: http://www.crocus.co.kr/391 ( + 마지막 팩토리얼 수 )

n!의 자릿수 :: http://www.crocus.co.kr/665

같은 내용을 알아봤고 이번에도 비슷하지만 조금 다른 문제를 알아보고자 한다.

코드를 바로 보자.

이 코드를 검증해 볼 수 있는 곳은 다음 주소를 통해 확인 할 수 있다.

http://codeforces.com/contest/869/problem/B

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <map>   using namespace std;   typedef long long ll;   ll a, b; ll tmp;   int main() {     scanf("%lld %lld", &a, &b);     tmp = 1;     for (ll i = a + 1; i <= b; i++)     {         tmp = (i % 10) * tmp;         tmp %= 10;           if (tmp == 0)             break;     }       cout << tmp << endl;       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus

우선 값 a, b를 받아 b! / a!을 해보려 한다.

for문에 의해 b * (b - 1) * ... * a + 1까지 곱하는 것을 의미하고 있다.

이때 tmp는 현재 i의 1의 자리수만 가져와서 tmp를 곱한 값을 처리한다.

그리고난 후 tmp는 또 1의자리만 가지게 된다.

결국 끝자리의 값이 뭔지 위와 같은 처리로 인해 파악할 수 있게 된다.

마지막으로 tmp가 0이 되는 순간이 있다면 끝자리가 0일때 어떤 수를 곱해도 0이므로 break해준다.

사실 이 알고리즘을 약간 더 생각해보면, b와 a의 차이가 10이상이 되면 무조건 답은 0이 된다.

그 이유는 n * (n-1) * .. * (n-9)에서 항상 끝자리가 2와 5의 곱이 나오기 때문이다.