작년 대전 리저널...

  • kjunking2002
    kjunking2002

    Binary Search Tree 라는 문제인데요...

    리스트로 트리 구연한다음에..말단 노드부터 올라오면서 다이나믹 테이블을 채워갔는데..

    9, 999, 991로 나눈 나머지를 출력해야 되는데 다이나믹 점화식에 나눗셈이 있는 바람에....난감하다는....ㅠㅠ

    도와주세요...


    11년 전
4개의 댓글이 있습니다.
  • Being
    Being

    문제가 기억이 나지 않지만, 일반적으로 9999991은 소수이므로 0이 아닌 수에 대해서는 곱셈에 대한 역원이 존재합니다. 예를 들어 x / 1823 대신 x * 2715302를 할 수 있습니다.

    그런데 왠지 느낌으로는 나눗셈 없이 구현하는 방법이 있을 것 같네요.


    11년 전 link
  • 김우현
    김우현
    1. 점화식에서 나눗셈이 나오지 않도록 변형할 수는 없을까요?

    2. 언급하신 9999991은 소수입니다. (이하, P라 언급하겠습니다.)
      점화식에 나눗셈이 있다고 하셨으니, 점화식은 f(n) = (g(n)/h(n)) % P 형태로 표현될거 같습니다.
      f(n)의 값이 항상 정수라면, A^(-1) = A^(M-2) (mod P) 라는 정리를 이용할 수 있을 것 같습니다.
      참고 : http://en.wikipedia.org/wiki/Modular_multiplicative_inverse


    11년 전 link
  • helloneo
    helloneo

    SRM 467 SuperSum 문제를 mod inverse 로 푼 사람이 많군요.. 코드를 참고하면 될듯..
    http://apps.topcoder.com/wiki/display/tc/SRM+467


    11년 전 link
  • hyunhwan
    hyunhwan

    제가 풀었던 방법으론 점화식에 나눗셈이 없었던 형태로 풀이가 가능했던 것으로 기억합니다.


    11년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.