13172번 - Σ
문제 핵심은 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 로 해당하는 부분을 없애면 같아집니다.
댓글을 작성하려면 로그인해야 합니다.
jcreate98 2년 전 13
문제 핵심은 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 로 해당하는 부분을 없애면 같아집니다.