4개의 댓글이 있습니다.

• 
  Being

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

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

  
  13년 전 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

  
  13년 전 link

• 
  helloneo

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

  
  13년 전 link

• 
  hyunhwan

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

  
  13년 전 link

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