소인수분해와 팩토리얼_알고리즘

소인수 분해

• 문제 링크
  • https://www.acmicpc.net/problem/11653
• 문제 풀이
  • 정수 N을 소수의 곱으로 분해
  • 소수를 구하지 않고도 해결 가능
  • N을 나눌수 없을 때까지 나누기
• 소스 코드

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(void) {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int>soinsu;

	int n=0;
	cin >> n;

	for (int i = 2; i*i <= n; i++) {
		while (n%i == 0) {
			soinsu.push_back(i);
			n /= i;
		}
	}

	sort(soinsu.begin(), soinsu.end());

	for (int i = 0; i < soinsu.size(); i++) {
		cout << soinsu[i] << '\\n';
	}

	if (n > 1)cout << n;
	return 0;
}

팩토리얼

• 문제링크
  • https://www.acmicpc.net/problem/10872
• 문제 풀이
  • 그냥 재귀로 0이 될때까지 -1 해주고 0일때 리턴은 1로 함
• 소스코드

#include<stdio.h>
#include<iostream>
using namespace std;
int factorial(int number) {
	if (number == 0) return 1;

	return number*factorial(number - 1);
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	cout << factorial(n);

	return 0;
}

팩토리얼 0의 개수

• 문제 링크
  • https://www.acmicpc.net/problem/1676
• 문제 풀이
  • 10! 인 경우 0이 몇개 일까?
    • 2개임
  • 10!을 소인수분해하면 알 수 있음
  • 10! = 123456789*10
  • 10! = 1232^252372^33^22*5
  • 10! = 2^83^45^2*7
  • 즉, 2^6 * 3^4 * 7 * 10^2
    • 이렇게 되는데 여기서 포인드 2와 5가 몇개 나오는지 알아야한다.
    • 5의 개수가 2의 개수 보다 작기 때문에 5의 개수를 세면됨 그것이 0의 개수가 됨
  • 5의 배수로 나눠지는 것의 몫의 개수를 더하면됨
  • 100이라면 100/5 = 20 + 100/25 = 4 = 24가됨
• 소스코드

#include<stdio.h>
#include<iostream>
using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n;
	cin >> n;
	int ret = 0;
	for (int i = 5; i <= n; i *= 5) {
		ret += n / i;
	}
	cout << ret << '\\n';
	return 0;
}

조합 0의 개수

• 문제 링크
  • https://www.acmicpc.net/problem/2004
• 문제 풀이
  • nCm의 식은 = n!/ m!(n-m)!
  • 팩토리얼의 경우 2의 개수가 5보다 많아서 5의 개수만 세면되는데
  • 조합의 경우 2와 5를 동시에 세어야함
  • 단 n!의 개수는 더하고 m!, (n-m)!의 경우는빼야함
    • 5^8 / 5^2 인 경우 우리는 5 ^(8-2)로 표기하기에 개수를 빼줘야하는 것
• 소스코드

#include<iostream>
#include<algorithm>
using namespace std;

long long cntHandler(int n, int m,int findNumber) {
	long long Cnt = 0;

	for (int i = findNumber; i <= n; i *= findNumber) {
		Cnt += n / i;
	}
	for (int i = findNumber; i <= m; i *= findNumber) {
		Cnt -= m / i;
	}
	for (int i = findNumber; i <= (n - m); i *= findNumber) {
		Cnt -= (n - m) / i;
	}
	return Cnt;
}

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, m;
	int result = 0;
	cin >> n >> m;

	result = min(cntHandler(n, m, 2), cntHandler(n, m, 5));

	cout << result << endl;

	return 0;
}