6484

팩토리얼로 나타났을 때, 소인수분해하기

에라토스테네체의 체
1. 처음에 다 default true로 하기
2. i*i < n 인 i 까지 반복(sqrt(N))
3. %i == 0 이면 false로 바꾸기

현재 위치가 소수이면 primes vector 배열에 넣기
소수가 아닌 것들은 bool값 바꿔주기

10억 7은 int 안으로 들어올 수 있다.
그러나 곱하는 계산 과정 속에서 int 범위 넘을 수 있다.
long long으로 사용해줘야한다!

그릐고 n을 나는 임시 변수로 저장하지 않아서 값이 바뀌었다.
그래서 제대로 된 답이 나오지 않았다.
변수를 그대로 사용할 때 뒤에서 다시 사용하면, 해당 값을 임시변수에 저장하여 사용하는 습관을 기르자.

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>

#define div (1000000007)
#define MAXN 100000
using namespace std;
bool isprime[MAXN + 1];
vector<int> primes;
int main(int argc, char** argv)
{
	int test_case;
	int T;
	freopen("input.txt", "r", stdin);
	cin >> T;
	//소수 전처리
	for (int i = 0; i <= MAXN; ++i) isprime[i] = 1; //모두 true로 초기화
	isprime[1] = false; isprime[0] = false;
	for (int i = 2; i * i <= MAXN; i++) {
		if (!isprime[i]) continue; //소수가 아니면 pass
		for (int j = i * i; j <= 100000; j += i) {
			isprime[j] = false;
		}
	}
	for (int i = 2; i <= MAXN; ++i) {
		if (isprime[i]) {
			primes.push_back(i);
		}
	}
	for (test_case = 1; test_case <= T; ++test_case)
	{
		int n, k;
		long long ans = 1;
		cin >> n >> k;
		//TODO: nCk 의 약수의 개수를 구하여라.
		//1. 소인수분해
		unordered_map <int, int> um; // 소수, 지수
		for (int prime : primes) {
			if (prime > n) break;
			int factor_cnt = 0;
            //n!
			int temp_n = n;
			while (temp_n) {
				temp_n /= prime;
				factor_cnt += temp_n;
			}
			//k!
			int temp_k = k;
			while (temp_k) {
				temp_k /= prime;
				factor_cnt -= temp_k;
			}
            //(n-k)!
			int temp_nk = n - k;
			while (temp_nk) {
				temp_nk /= prime;
				factor_cnt -= temp_nk;
			}

			if (factor_cnt > 0) {
				long long tmp = (factor_cnt + 1) % div;
				ans = (ans * tmp) % div;
			}
		}

		cout << "#" << test_case << " " << ans << "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}