글 읽기 - Big-O(n) 풀시 버그

leehanjun 5년 전 0

안녕하세요.

여러분들의 조언을 듣고자 글을 올립니다.

이 문제를 모듈러 공식 성질을 이용해서 풀려고하는데, 이슈가 있어서 질문을 합니다.

공식.

a * b = r_a * r_b (mod n)

코드는 아래와 같습니다.

버그가 발생하는 지점은 float 계산에서 문제가 발생하는 것 같은데,

해결할 수 있는 방법이 있을까요???

#!/usr/bin/python

# 이항 계수2
# 
# Modular

# def. 
# a = n*m + r
# a mod n = r

# formula.
# a*b = r_a*r_b (mod n)

import sys, math

sys.setrecursionlimit(10000)

CONST_MOD = 10007

def modFactorial(n, k):
    # Basis
    if n == 1:
        return 1

    # Algorithm - use the formula
    # 1 <= n <= 1000
    ret = 1
    for temp in range(1, k+1):
        ret *= ((n - k + temp)/temp) % CONST_MOD        # 버그 발생

    return ret % CONST_MOD

n, k = input().strip().split()
n = int(n)
k = int(k)

# get answer
print(math.ceil(modFactorial(n, k)))


# Debug

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

문제

문제

출처

ICPC

Big-O(n) 풀시 버그

leehanjun 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말