13172번 - Σ
문제를 읽고 이해한 바로는 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) 임은 확인했는데
문제에서 설명한 수식을 잘 못 이해해서 틀리게 구현한건지 잘 모르겠습니다.
제가 답안을 제출하진 않았지만 line 29가 의심되네요
각 분수마다 답을 구해서 다 더하면 되는 것이 아니고, 모든 분수를 다 더한 답의 분모와 분자를 각각 mod한 것에 대해 구해야 합니다.
a/x + b/y = (ay + bx)/xy 를 이용해서 더해나가고, 더할 때마다 분모 분자를 각각 mod 처리해서 진행하면 됩니다.
각각 더해도 상관없습니다.
그렇군요. 모듈러만 잘 쳐주면 되는 거군요. 감사합니다.
답변 감사합니다.
하지만 제가 적은 해법이 맞다면, 29번째 줄이 질문에 기술한 풀이와 어떻게 다른지 아직 잘 모르겠네요 ㅠ
그 ans값이 매우 커질 수 있기 때문에, 더하면서도 모듈로를 해줘야 합니다.
아.. 감사합니다!
m * convert의 리턴값을 long long int 로 충분히 담을 수 있어서 모듈러 연산을 안해주었는데
문제에서 요구하는 답은 해주는게 맞겠네요.
댓글을 작성하려면 로그인해야 합니다.
tofhddl9 4년 전 1
문제를 읽고 이해한 바로는 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) 임은 확인했는데
문제에서 설명한 수식을 잘 못 이해해서 틀리게 구현한건지 잘 모르겠습니다.