[C/C++] 백준 #2553 마지막 팩토리얼 수(수학)

이번 문제는 수학의 구조를 잘 알고 있으면 크게 문제 없이 풀 수 있습니다. 

 

https://www.acmicpc.net/problem/2553

2553번: 마지막 팩토리얼 수

 

이번 문제는 팩토리얼 계산을 하고, 마지막에 연속된 0을 제외한 마지막 숫자를 출력하는 프로그램입니다.

 

factorial

 

프로그램으로 작성할 때에는 2라는 소인수와 5라는 소인수를 미리 제거하고, 끝자리만 계산하시면 됩니다.  2의 소인수의 개수가 5의 소인수의 개수보다 크므로, 나머지 2의 소인수의 개수를 가지고 최종 계산을 해주면 됩니다.  사실 2의 거듭제곱을 하면, 끝자리 숫자가 2, 4, 8, 6 을 반복하기 때문에 이를 이용하면 루프를 돌리지 않아도 됩니다.

 

프로그램은 더 효율적으로 작성할 수 있겠지만, 어차피 실행시간은 0ms가 나와서 놔두었습니다.

//------------------------------------------------
//    baekjoon #2553
//        - by Aubrey Choi
//        - created at 2019-08-17
//------------------------------------------------
#include <stdio.h>

int fact0(int n)
{
    int twos=0, f=1, c;
    for(int s=n; s; s/=2) twos+=s/2;
    for(int s=n; s; s/=5) twos-=s/5;
    for(int i=3;i<=n;i++) { c=i; while(c%2==0) c/=2; while(c%5==0) c/=5; f=(f*c)%10; }
    while(twos--) f = (f*2)%10;
    return f;
}

int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", fact0(n));
}