https://www.acmicpc.net/problem/24503
문제요약
- K가 주어짐(10^15), A가 주어짐(10^15)
- A * X! 이 K의 배수가 되는 가장 작은 X 구하기
- 공식해설
접근법
- 팩토리얼 연산을 통해 K만 갖고 있는 것(소인수)을 채워야함
- K 만 갖고 있는 것 : K / gcd(K, A)
- 3 ^ 5을 K만 갖고 있다면, 3, 6, 9, 12 만에 채울 수 있음. 즉 3의 배수가 팩토리얼에 나타날때마다 채울 수 있는데 9(=3 * 3)와 같은 경우도 고려해보야함
- 각각의 소수별로 따로 만족할 것이고, 그 중에 가장 큰 것을 구하면 될 것임
- K / gcd(K, A) 소인수 분해를 매번해야하는가?
- 처음에 여기서 막혔음
- sqrt(10^15)까지의 소수를 미리 구하고(300만개 정도), 매번 소인수 분해를 하려고 했음 => 시간 복잡도 문제
- 공식해설을 살짝 참고했고, 아이디어를 얻음
- 어짜피 K의 소인수는 정해져있고, 이들만 소인수 분해에 이용하면 됨
- K / gcd(K, A)에서 소인수들이 몇번 나타나는지 계산함
- 나타난 소인수를 만족하기 위해서 어디까지 팩토리얼해야하는지 각각 계산함
- 계산한 것 중에 최대가 구하고자 하는 값
newbieski