tofhddl9   4년 전

문제를 읽고 이해한 바로는  S1/N1 + S2/N2 + ... + SM/NM  계산의 어려움 때문에

임의의 분수 a / b를 모듈러를 이용해 (a * b-1 mod x)의 정수 값으로 계산을 하는 것이고

기대값의 선형성에 의해 주어진 m개의 모든 분수에 대해 값을 구해 모두 더한것을 답이라 생각했습니다.

b-1는 페르마 소정리를 이용해 나온  bX - 2 ≡ b-1 (mod X)를 이용해 b1e9+7-2 mod X 를 구했습니다.

여러 케이스에서 직접 구한  b-1으로 b *  b-1  ≡ 1(mod X) 임은 확인했는데

문제에서 설명한 수식을 잘 못 이해해서 틀리게 구현한건지 잘 모르겠습니다.

tjdans1114   4년 전

제가 답안을 제출하진 않았지만 line 29가 의심되네요

djm03178   4년 전

각 분수마다 답을 구해서 다 더하면 되는 것이 아니고, 모든 분수를 다 더한 답의 분모와 분자를 각각 mod한 것에 대해 구해야 합니다.

a/x + b/y = (ay + bx)/xy 를 이용해서 더해나가고, 더할 때마다 분모 분자를 각각 mod 처리해서 진행하면 됩니다.

tjdans1114   4년 전

각각 더해도 상관없습니다.

djm03178   4년 전

그렇군요. 모듈러만 잘 쳐주면 되는 거군요. 감사합니다.

tofhddl9   4년 전

답변 감사합니다.

하지만 제가 적은 해법이 맞다면, 29번째 줄이 질문에 기술한 풀이와 어떻게 다른지 아직 잘 모르겠네요 ㅠ

djm03178   4년 전

그 ans값이 매우 커질 수 있기 때문에, 더하면서도 모듈로를 해줘야 합니다.

tofhddl9   4년 전

아.. 감사합니다!

m * convert의 리턴값을 long long int 로 충분히 담을 수 있어서 모듈러 연산을 안해주었는데

문제에서 요구하는 답은 해주는게 맞겠네요.

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