##

  • 끝자리 0의 개수는 해당 값을 소인수 분해를 했을 때 2와 5의 개수로 인해 결정된다. (2와 5의 개수의 최솟값)
  • 조합은 nCr = ${\frac{n!}{r!(n-r)!}}$
  • ${n!}$은 1에서부터 n까지의 수가 모두 들어 있다.
  • n보다 작은 5의 제곱수들로 나누어 그 몫을 모두 더하면 ${n!}$의 5의 개수를 의미한다.
    • e.g 25!에는 25, 20, 15, 10, 5와 같이 5개의 5의 배수가 존재하고, 25를 5, 25로 각각 나누면 그 몫이 5와 1이 나온다. 5와 1을 합한 6이 25!의 5의 개수이다.
  • n!, r!, (n-r)! 각각의 5의 개수, 2의 개수를 구한다. n!의 5의 개수에서 r!의 5의 개수를 빼고, (n-r)!의 5의 개수를 뺀다.
    2의 개수도 마찬가지로 구한다.
  • 5의 개수와 2의 개수 중 더 작은 값이 끝자리 0의 개수이다.


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



#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cmath>

using namespace std;

#define ll long long

int N, R;

ll cal(int num, int div) {
	ll cnt = 0;
	while (num > 0) {
		cnt += num / div;
		num /= div;
	}
	return cnt;
}

ll solution() {
	ll cnt2 = cal(N, 2) - cal(R, 2) - cal(N-R, 2);
	ll cnt5 = cal(N, 5) - cal(R, 5) - cal(N-R, 5);
	
	return min(cnt2, cnt5);
}

int main() {
	scanf("%d%d", &N, &R);
	printf("%lld\n", solution());
}