jcreate98   2년 전

문제 핵심은 a/b + c/d = (d*a + b*c) / b*d 계산이기 때문에, 단순히 b*d 와 (d*a + b*c) 만 계산하면 되는 문제입니다.  

하지만 이 숫자가 long long 범위 안에 있다는 보장이 없기 때문에  ( ex : 1/1000000007, 1/1000000009, 1/1000000021, 1/1000000033, ... )

다른 방법이 필요하고 그 방법을 찾는게 목표입니다.


그러면 여기서 나온 대로 계산하려면 다음을 보여야하는데,

a * b^-1 (mod m) + c * d ^ -1 (mod m) = (d*a + b*c) * (b*d) ^ -1 (mod m)

->

a * b ^ (m-2) (mod m) + c * d ^ (m-2) (mod m) = (d*a + b*c) * (b*d) ^ (m-2) (mod m)

우측 정리하면 

a * b ^ (m-2) * d ^ (m-1) (mod m) + c * d ^ (m-2) * b ^ (m-1) (mod m) 

이 되고 임의의 숫자 n에 대해

n ^ (m-1) (mod m) = 1 로 해당하는 부분을 없애면 같아집니다.

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