2004 조합 0의 개수

끝자리에 있는 연속된 0의 개수를 찾는 문제다. 0이 나온다는 것은 10이 곱해졌는 얘기고, 10을 소인수분해하면 2, 5의 인수가 나오기 때문에 2, 5 중 최소 개수를 찾으면 된다

 

N 제한이 20억이기 때문에 20억을 모두 탐색하면서 나머지 연산을 할 수는 없다

빠르게 2, 5의 개수를 찾는 방법

[참고] https://ksj14.tistory.com/entry/BackJoon1676-%ED%8C%A9%ED%86%A0%EB%A6%AC%EC%96%BC-0%EC%9D%98-%EA%B0%9C%EC%88%98

 

따라서 조합은 nCr = n! / ((n-r)!*r!) 이므로 각 값에 해당하는 2, 5의 개수를 각각 배열에 담아서 저장해서 마지막에 계산하면 된다. 분자와 분모는 -관계이기 때문에 빼주면서 최소값을 찾으면 된다

 

문제: https://www.acmicpc.net/problem/2004

깃허브주소: https://github.com/surinoel/boj/blob/master/2004.cpp

 

	#include <iostream>
	#include <algorithm>
	using namespace std;
	typedef long long ll;
	ll ans[3][2];
	void calc(ll idx, ll k) {
	for (ll i = 2; i <= k; i *= 2) {
	ans[idx][0] += k / i;
	}
	for (ll i = 5; i <= k; i *= 5) {
	ans[idx][1] += k / i;
	}
	}
	int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	ll n, m;
	cin >> n >> m;
	calc(0, n);
	calc(1, m);
	calc(2, n - m);
	cout << min(ans[0][0] - ans[1][0] - ans[2][0],
	ans[0][1] - ans[1][1] - ans[2][1]) << '\n';
	return 0;
	}

view raw 2004.cpp hosted with ❤ by GitHub