kwl3434   5년 전

공식이 있을꺼같은데 도저히 생각이 안납니다.....

잠이 안오고... 가슴이답답하고...울고싶다..

eric00513   5년 전

아 이 문제는 제가 만들어서 잘 알아요. 이 문제는 절대 팩토리얼을 구하시면 안 됩니다. N의 범위가 2^31 미만인데, 당연히 시간 초과가 나겠죠. 정수론을 아신다면, 쉽게 푸실 거에요.

eric00513   5년 전

P.S. 공식은 있습니다. VP(N) 이런 게 있을거에요.

kwl3434   5년 전

정말 감사합니다ㅠㅠ 공식을 아무리 찾아봐도 관련된걸 못찾겠어서 슬퍼하고있었어요ㅠ

eric00513   5년 전

해법을 알려드리자면, 팩토리얼을 구하지 마시고, 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년 전

소름이 돋습니다ㅎㅎㅎㅎ 기분좋게 잘수있어 기쁘네요 감사합니다!

kwl3434   5년 전

아까 알려주신거에서 2로 나눈 몫이라고 하신거   A를 2로 잘못쓰신거같아요! 한수 배우고 갑니다~

eric00513   5년 전

죄송합니다. 그래도 문제는 풀 수 있을 거에요!!!

댓글을 작성하려면 로그인해야 합니다.