[백준] 11790. Primorial vs LCM

newbieski·2022년 3월 3일

백준

목록 보기

120/210

문제 요약

접근법

LCM은 소수들로 구성될 것임. 소수별 가장 큰 거듭제곱이 들어갈 것임
- 숫자들에 ${2^1, 2^0, 2^2, 2^{10}, ...}$ 이 포함되었다고 치면 LCM에는 ${2^{10}}$ 만 들어가면 됨
어짜피 소수들로 또 나눌테니까 1승으로 들어간 것들은 삭제될 것임
제곱 이상으로 들어갈테니까... 대략 10^7 아래의 소수들만 일단 살펴보면 됨
10^7 이하의 소수들을 구해보면 대략 60만개 정도 되고, 각각의 소수들이 N에 최대 몇승으로 들어가는지 계산해서, 거듭제곱 시키고, 곱하고, MOD에서 답은 구할 수 있겠음
그런데 이렇게 하면 테스트케이스(5만) 소수(60만) 몇승인지 계산(logN) 하면 엄청 큼

관찰

2는 10^14인 경우 대략 40여번 들어갈 것임
4는 20여번, 16은 10여번, ... 일단 숫자가 많이 줄어들긴 함
p가 2번 들어간다고 치면, 2번 들어가는 것을 일일이 구하는 것은 힘들지도 모름 => 대충 큰 어떤 소수가 몇번 들어가는지 봐서 2번이면 더 키워보고, 1번이면 줄여보고... => 이분 탐색
이분탐색으로 k번 들어가는 소수가 어디서부터 어디까지인지는 구하겠음
구했는데 곱은???? 일일이 다 곱함???
- 누적 곱을 누적 곱으로 나누면 좋겠음 : MOD에서 나누기 = 역원 곱셈 = 역원도 누적곱해놓고 이용해도 되겠음 ==> 이렇게는 안함
- 구간 누적곱을 구해놓음 => 구간트리, 인덱스트리, 세그먼트 트리

복잡도

T X (판단할 소수들(40 -> 20 -> ... : 대략 logN) X 소수별로 몇 거듭제곱인지 판단(logN) + 구간곱(log(소수개수) < logN) = O(T X logN X logN)

다른 접근법

이렇게 푸는게 정석인 것 같음
소수별로 나타나는 "허들"이 있음
- 2 -> 2, 2^2 -> 4, 2^3 -> 8
- 3 -> 3, 3^2 -> 9, 3^3 -> 27
N까지 소수들의 곱이니까, N이 저 숫자들 보다 크면 LCM에 소수들이 저만큼 포함되는 것을 보장
- N = 9면, 2^3포함, 3^2 포함 이런 식
N에 대해 소수별로 일일이 탐색? 그러기엔 소수가 60만개임
"섞는다"
- 2가 나타날때 2를 추가, 3이 나타날때 3을 추가, 4가 나타날때 2를 더 추가, 8이 나타날때 2를 더 추가, 9가 나타날때 3을 더 추가...
- "허들" 순서대로 "소수"를 추가시켜 나감
- 그러면 X가 되었을때 누적해서 추가된 소수를 알 수 있음 => LCM을 알게됨 => N보다 작거나 같은 X를 찾으면 LCM을 구함 => lower_bound
  - [2] = 2
  - [3] = 2 x 3
  - [4] = 2 x 3 x 2
  - [5] = 2 x 3 x 2 x 5
  - [7] = 2 x 3 x 2 x 5 x 7
  - [8] = 2 x 3 x 2 x 5 x 7 x 2
  - [9] = 2 x 3 x 2 x 5 x 7 x 2 x 3
- 어짜피 LCM을 소수들로 나눌 것이기 때문에 등장하는 것을 "한단계"씩 낮추면 자연스럽게 답을 구함
  - 2 -> 4, 2^2 -> 8
  - 3 -> 9, 3^2 -> 27