[C++] 백준 1010번: 다리 놓기

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

1010번: 다리 놓기

아이디어

정석대로 계산하려면 long long 범위도 초과한다. \(\prod_{i=M-N+1}^{M}{i}\)의 인수 목록에서 \(\prod_{i=1}^{N}{i}\)와의 공통 인수를 제거하여 답을 도출해야 한다.

풀이

\(M-N+1\)부터 \(M\)까지의 각 \(i\) 마다의 인수를 구해 맵에 저장했다. key에는 인수를, value에는 인수의 개수를 저장했다. 이후 \(1\)부터 \(N\)까지의 각\(i\)에서 인수를 구하는데, 이번에는 인수의 개수를 하나씩 감소시켜 나간다. 이 과정을 거친 후 맵의 각 key를 각 value만큼 곱하여 답을 구하면 된다.

코드

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int T, N, M;
	
	cin >> T;
	while (T--) {
		cin >> N >> M;

		map<int, int> factors;

		for (int i = M - N + 1; i <= M; i++) {
			int _i = i;
			for (int j = 2; _i > 1; j++)
				while (_i % j == 0) {
					_i /= j;
					factors[j]++;
				}
		}

		for (int i = 2; i <= N; i++) {
			int _i = i;
			for (int j = 2; _i > 1; j++)
				while (_i % j == 0) {
					_i /= j;
					factors[j]--;
				}
		}

		int result = 1;
		for (auto& factor : factors) {
			auto [key, val] = factor;
			while (val--)
				result *= key;
		}

		cout << result << EL;
	}

	return 0;
}