[C++/백준 2004번] 조합 0의 개수

2024. 10. 26. 14:21·프로그래밍 공부/백준 (C++)

 

 

 

조합 공식과 정수론을 이용해 해결하는 문제.

 

조합 공식은 nCr n! / (n-r!) r! 이다. 

 

그리고 10을 구성하는 소인수는 2 x 5 인데, 2와 5 소인수 중 개수가 작은 것이 0의 개수가 될 것이다. 

 

팩토리얼의 소인수를 구하는 방법은 

https://blog.naver.com/shalska1234/50087466089

 

계승(factorial, !)의 소인수분해!

계승 [階乘, factorial] 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 말하며 n!로 나타낸다....

blog.naver.com

 

이 블로그 게시글을 참고했다. 

 

100! -> 100 / 2, 100 / 4, 100/ 8 , 100 / 16  , 100 / 32 , 100 / 64 의 값을 모두 더하면 2의 소인수 개수가 된다.

 

따라서 n! 의 2 소인수 개수 - (n!-r!) 의 2 소인수 개수 - r ! 의 2 소인수 개수 를 해주면 해당 조합의 2 소인수 개수가 나온다. 

5도 똑같은 방식으로 적용하여 계산하면 문제를 해결할 수 있다.

 

 

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

long long d2(long long input)
{
	long long cnt = 0;
	for (long long i = 1; i <= input; i *= 2)
	{
		if (i > input) break;
		cnt += input / i;
	}
	return cnt;
	
}

long long d5(long long input)
{
	long long cnt = 0;
	for (long long  i = 1; i <= input; i *= 5)
	{
		if (i > input) break;
		cnt += input / i;
	}
	return cnt;
}


int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	long long n, m;
	long long count = 0;
	cin >> n >> m;


	count = min(d5(n) - d5(m) - d5(n - m), d2(n) - d2(m) - d2(n - m));
	


	cout << count;
}

 

 

 

 

 

'프로그래밍 공부 > 백준 (C++)' 카테고리의 다른 글

[C++/백준 17087번] 숨바꼭질 6  (0) 2024.10.26
[C++/백준 9613번] GCD 합  (0) 2024.10.26
[C++/백준 6588번] 골드바흐의 추측  (0) 2024.10.25
[C++/백준 1918번] 후위 표기식  (0) 2024.10.25
[C++/백준 1935번] 후위 표기식 2  (0) 2024.10.24
'프로그래밍 공부/백준 (C++)' 카테고리의 다른 글
  • [C++/백준 17087번] 숨바꼭질 6
  • [C++/백준 9613번] GCD 합
  • [C++/백준 6588번] 골드바흐의 추측
  • [C++/백준 1918번] 후위 표기식
Rocketbabydolls
Rocketbabydolls
Rocketbabydolls
  • Rocketbabydolls
    With The Lights Out
    Rocketbabydolls
  • 전체
    오늘
    어제
    • 전체글 (183) N
      • 프로그래밍 공부 (117)
        • C (16)
        • Jumping into C++ (9)
        • MFC (C++) (1)
        • 자료구조 (1)
        • 알고리즘 (1)
        • 백준 (C++) (74)
        • 핸즈온 머신러닝 2판 (6)
        • Unseen 3기 준비 (4)
        • 원티드 포텐업 게임 개발자 양성과정 2기 (4)
      • 언리얼엔진5 (62) N
        • [Part1] 이득우의 언리얼 프로그래밍 (12)
        • [Part2] 이득우의 언리얼 프로그래밍 (2)
        • [Part2 복습] 이득우의 언리얼 프로그래밍 (3)
        • [Part3] 이득우의 언리얼 프로그래밍 (14)
        • [Part4] 이득우의 언리얼 프로그래밍 (0)
        • FPS 게임 1인 프로젝트 (6)
        • 각종 지식 (10) N
        • 블루프린트 Paper2D 로 게임 만들기 (14)
        • 팀 프로젝트 (1)
      • 일상 (1)
      • ETC (1)
        • 맥북 (1)
  • 블로그 메뉴

    • 링크

    • 공지사항

    • 인기 글

    • 태그

      실전C프로그래밍 나중채
      티스토리챌린지
      핸즈온 머신러닝 2판
      실전C프로그래밍 실습문제
      실전 C프로그래밍 나중채
      언리얼엔진 옵저버 패턴
      언리얼엔진 디자인 패턴
      핸즈온 머신러닝
      언리얼엔진
      언리얼엔진5 fps 프로젝트
      c언어
      C언어 실습문제
      오블완
      c++ 17298
      실전 C프로그래밍 실습문제
      언리얼엔진5
      실전C프로그래밍
      실전 C프로그래밍
      언리얼엔진 중재자 패턴
      실전 C 프로그래밍
    • 최근 댓글

    • 최근 글

    • hELLO· Designed By정상우.v4.10.3
    Rocketbabydolls
    [C++/백준 2004번] 조합 0의 개수
    상단으로

    티스토리툴바