FBC #1

dohoon·2021년 3월 9일
0
post-thumbnail

tistory에서 옮겨왔습니다

후기
오늘은 신정이라서 사실 참여하신 분이 두 분 밖에 없다...
그래도 열심히 풀어주신 두 분께 감사를 표한다.
새해에도 다들 열공해서
각자가 원하는 목표를 달성하는 한 해가 되길 바란다.

*오늘 셋에서는 솔직히
B, E가 제일 값진 문제들이였다.

이번 주말은 뭔가 바쁜 것 같으면서도 바쁘지 않게 지나가는 바람에 풀이가 늦어졌다.
벌써 근무 태만인가 두렵지만, 이번 포스팅은 beginner contest라 의욕을 가지고 빠르게 작성할 수 있겠다.
그리고 무엇보다 풀이 작성 속도가 빨라졌다:)

Ⓐ 약수 (1037)

by hgmhc
엄청나게 빠른 속도로 풀어내려 했지만, 실상은 왜맞틀을 엄청나게 외쳤다...
당연히 최소공배수를 떠올리셨을 것이다.

이 때 좋은 함수가 하나 있다. 클래스에 있는 lcm함수이다.
아마 C++2020에서 업데이트가 되었나 그랬던 것으로 알고있다.

A가 1과 N이 아니여야 한다가... 왜맞틀의 요인이 되었다.
lcm을 돌려 나온 결과가 NN이 되기 위해서는 N=pkN=p^k꼴이 되는 수밖에 없다.
따라서 pk1p^{k-1}도 등장했을 것임이 확실해진다.
이 생각을 통해 mmmin_min\_을 만들어(각각 최대, 최솟값이다) 결과가 겹치게 되는 경우 가장 작은 수인 pp로 나누어 주게 만들었다.

Ⓑ 연구소 (14502)

Ⓒ 조합 0의 개수 (2004)

by hgmhc
수학적 지식이 → 있다면 확신을 가지고 바로 문제 풀이에 임할 수 있다.
ㅤㅤㅤㅤㅤㅤㅤ→ 없다면 살짝의 수학적 감으로 문제 풀이에 임할 수 있다.

long long 범위를 잡지 않으면 틀릴 수 있다.
우선 틀렸다면 그것부터 확인해보시길 바란다.

기본적으로,
n!=p1e1×p2e2×n!=p_1^{e_1}\times p_2^{e_2}\times \cdots로 소인수 분해되었을 때,
eie_i을 구하는 방법을 안다면 이 문제를 풀 수 있음을 알아햐 한다.
왜냐하면 22의 지수와 55의 지수 중 더 작은 것을 택해주면 될 것이기 때문이다.

eie_i를 구하기 위해서는, 1,2,,n1, 2, \cdots, n 중에 aa의 배수가 몇 개 있을까를 먼저 떠올려보자.
na\left \lfloor \frac {n}{a} \right \rfloor임을 알 수 있다.
그렇다면 k×pk\times p 꼴은 총 np\left \lfloor \frac {n}{p} \right \rfloor개이다.

그런데, !!을 계산하기에는 뭔가 빼먹은 느낌이 있다.
그렇다. pαp^\alpha을 인수로 지니는 수들은 더 세주어야 할 것이다.

그러기 위해서는 그저 pp가 있던 자리에 p2,p3,p^2, p^3, \cdots만 대입해서 싹 다 더해주면 충분할 것이다.

이를 구현한 코드이다. 질문이 있으면 댓글이나 DM!

Ⓓ 집합의 표현 (1717)

by hgmhc
서로소 집합 또는 union-find 등의 이름으로 불리우는 자료구조를 소개하기 위한 문제이다.
만약 이를 사용하지 않고 구현하였다면 꼭 더보기를 통해 확인하길 바란다.
그리고 앞으로는 통상적으로 불리우는 용어인, DSU(Disjoint Set Union)이라는 이름으로 통일할 것이다.

DSU는 상당히 중요한 개념이므로,
다음의 링크를 방문하여 배워보시길 추천드립니다. (갓라이...)
물론, 나중에 시간이 된다면 모르고리즘에도 DSU 개념 글을 올려보도록 하겠습니다.

확인해보셨다면 다음 코드를 이해하는 것은 어렵지 않을 것입니다.

Ⓔ 연결 요소의 개수 (11724)

by hgmhc
dfs로 방문한 곳은 0, 처음 가는 곳은 1을 반환함으로서 쉽게 풀 수 있습니다.
dfs 구현 자체에 어려움이 있으신 분들은 DM을 남겨주세요.

그렇지 않으시다면 코드를 이해하는데 아무 무리가 없으실 겁니다.

-끄읕-

profile
이 블로그 관리 안 한지 오래됨 / 백준 dohoon

0개의 댓글