사용자 도구

사이트 도구


ps:problems:boj:11439

이항 계수 5

ps
링크acmicpc.net/…
출처BOJ
문제 번호11439
문제명이항 계수 5
레벨플래티넘 4
분류

수학, 정수론

시간복잡도O(nloglogn)
인풋사이즈n <= 4*10^6
사용한 언어Python
제출기록66524KB / 560ms
최고기록560ms
해결날짜2021/01/24

풀이

  • 이항 계수 4와 마찬가지로 이항계수를 일반적이지 않은 모듈러스로 나눈 나머지를 구하는 문제이다. 이항 계수 4에서는 모듈러스가 그나마 소수였지만, 이번에는 합성수이다.
  • 이것에 대한 풀이는 이항 계수를 임의의 합성수로 나눈 나머지 참고. 거기서 설명한 대로 시간 복잡도도 O(nloglogn)이다

코드

"""Solution code for "BOJ 11439. 이항 계수 5".

- Problem link: https://www.acmicpc.net/problem/11439
- Solution link: http://www.teferi.net/ps/problems/boj/11439
"""

from teflib import numtheory


def main():
    N, K, M = [int(x) for x in input().split()]
    if K > N - K:
        K = N - K
    ans = 1
    for p in numtheory.prime_list(N):
        prime_pow = p
        e = 0
        while prime_pow <= N:
            e += (N // prime_pow) - (K // prime_pow) - ((N - K) // prime_pow)
            prime_pow *= p
        ans = ans * pow(p, e, M) % M
    print(ans)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
M D B​ O X
 
ps/problems/boj/11439.txt · 마지막으로 수정됨: 2021/01/31 15:59 저자 teferi