[BOJ 1564] 팩토리얼5

 

 

문제 링크

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

1564번: 팩토리얼5

---

필요한 지식

 

• 모듈러 연산의 성질

$$(A*B) modC=((A mod C)*(B mod C)) mod C$$

 

곱셈에 대한 증명은 아래와 같으며 모든 사칙연산에 대해 성립한다.

 

---

주의할 점

• 문제에서 0이 아닌 뒤 다섯자리를 요구하기 때문에 MOD를 1e5로 잡을지도 모른다.
  하지만 xxxx50272 * 9500을 세로식으로 계산하면, xxxx7854000까지만 알 수 있다.
  즉 뒤의 이어지는 0을 모두 지울 경우 7, 8, 5, 4 네 개의 수만을 알 수 있는 것이다.

 

• 그렇기 때문에 넉넉히 MOD값은 넉넉히 잡아주고 답을 출력할 때 1e5로 나누어주자.

 

---

소스코드

#include <cstdio>

long long int n, t = 1;
const long long int MOD = 1e12;
void f()
{
    while (t % 10 == 0) {
        t /= 10;
    }
}
int main()
{
    scanf("%lld", &n);
    for (long long int i = 1; i <= n; ++i) {
        t *= i;
        f();
        t %= MOD;
    }
    printf("%05lld", t%100000);
    return 0;
}

 

 

 

 

 

공부한 것을 정리하기 위한 기록입니다.

상냥한 피드백은 감사히 받겠습니다.