[백준] 1564번: 팩토리얼5

Solved.ac 실버2
https://www.acmicpc.net/problem/1564

설명

팩토리얼5란, N!의 0이 아닌 뒤 5자리를 말한다. N이 주어졌을 때, 팩토리얼5를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N이 주어진다. N은 1,000,000보다 작거나 같다. 또, 9보다 크거나 같다.

출력

첫째 줄에 N의 팩토리얼5를 계산한다.

해결 Tip

알고리즘 분류

• 수학
• 정수론

팩토리얼이니 모듈러 연산만 해주면 나머진 쉽게 접근할 수 있다. 하지만, 그 모듈러 연산이 문제이다.
예를 들어, 나누는 수를 10만으로 잡으면, 9499!을 팩토리얼5로 표현했을 때 "xxxx50272"이다.
이때 9500을 곱해주면, "xxxx78540000"이 되면서 실제론 "7854"만 남게 된다.

결국, 나누는 수가 너무 작으면 연산하는 과정에서 오차가 발생할 수 있다. 따라서 연산할 땐, 나누는 수를 크게 잡아서 계산하고 마지막에 출력할 때만 5자리만 출력되도록 작성하면 된다.

코드

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

typedef long long int lli;

int main() {
    
    // init
    // fastio;
    lli N;
    scanf("%lld", &N);

    // solve
    lli ans = 1;
    for (lli i=2 ; i <= N ; i++) {
        ans *= i;
        while (ans%10 == 0)
            ans /= 10;
        ans %= (lli) 1e12;
        // cout << "[" << i << "] " << ans << '\n';
    }

    // print
    printf("%05lld", ans%100000);

    return 0;
}