아 이 문제는 제가 만들어서 잘 알아요. 이 문제는 절대 팩토리얼을 구하시면 안 됩니다. N의 범위가 2^31 미만인데, 당연히 시간 초과가 나겠죠. 정수론을 아신다면, 쉽게 푸실 거에요.
15996번 - 팩토리얼 나누기
해법을 알려드리자면, 팩토리얼을 구하지 마시고, VP(N)공식에 의하면, A의 배수가 N!에 몇 번 있는지를 구하는 것과 같습니다. 따라서 N이하의 A의 배수가 몇 개, N이하의 A^2의 배수가 몇 개, A^3의 배수가 몇 개 이런 식으로 구하면 됩니다. 그럼 또 A^(어쩌구 저쩌구)가 int나 long long을 넘어갈 수 있잖아요, 여기에서 신기한 규칙이 있습니다. A^2의 배수의 개수는 A의 배수의 개수를 2로 나눈 몫입니다. A^3의 배수는 A^2의 배수의 개수를 2로 나눈 몫입니다. ....이젠 코딩만 하면 될 것입니다.
댓글을 작성하려면 로그인해야 합니다.
kwl3434 5년 전 1
공식이 있을꺼같은데 도저히 생각이 안납니다.....
잠이 안오고... 가슴이답답하고...울고싶다..