BOJ 9693 : 시파르

• 문제 링크 : boj.kr/9693
• 난이도 : S4
• 태그 : 정수론

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T = 1;
    while(true) {
        int n;
        cin >> n;
        if(n == 0) break;
        int ans = 0;
        while(n) {
            ans += n / 5;
            n /= 5;
        }
        cout << "Case #" << T++ << ": " << ans << "\n";
    }
    return 0;
}

---

풀이

N!가 10으로 몇 번이나 나누어지는지 찾는 문제이다.

10은 2*5이고, 따라서 N!가 10으로 나누어지는 횟수는 N!의 약수가 몇 개의 2와 몇 개의 5로 이루어져 있는지 확인하면 된다.

N!안에는 2의 약수보다 5의 약수가 더 적을 수 밖에 없으므로 5의 약수의 개수를 세면 된다.

1~N까지 직접 5로 나눠보며 약수를 세어도 되지만, 더 쉽게 세는 방법이 있다.

5, 10, 15, 20, 25, ... 은 약수로 5를 갖는다. 따라서 5개의 정수마다 약수에 5가 하나씩 추가된다.

25, 50, 75, 100, ... 은 약수로 5^2를 갖는다. 따라서 5^2개의 정수마다 약수에 5가 하나씩 추가된다.

동일하게 5^K개의 정수마다 약수에 5가 하나씩 추가된다.

최종적으로 5의 약수의 개수는 N/5 + N/5^2 + N/5^3 + ... 이다.