문제

https://www.acmicpc.net/problem/13172
골드 IV

코드 (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    private static final long X = 1000000007;

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int M = Integer.parseInt(br.readLine());

        long result = 0;

        for (int i = 0; i < M; ++i) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            long  Ni = Long.parseLong(st.nextToken());
            long Si = Long.parseLong(st.nextToken());

            //reduce fraction number.
            long NS_gcd;
            if (Si > Ni) NS_gcd = gcd(Si, Ni);
            else NS_gcd = gcd(Ni, Si);
            Ni /= NS_gcd;
            Si /= NS_gcd;

            //obtain modulo inverse
            long Ni_inv = mypow(Ni, X-2);
            result += (Si * Ni_inv) % X;
            result %= X;
        }

        System.out.print(result);

    }

    private static long gcd(long a, long b) {
        if (a % b == 0) {
            return b;
        }
        return gcd(b, a % b);
    }

    private static long mypow(long a, long b) {
        if (b == 1) {
            return a;
        }

        long res1 = mypow(a, b / 2);
        res1 = (res1 * res1) % X;
        if (b%2 == 1) {
            res1 = (res1 * a) % X;
        }
        return res1;
    }
}

풀이

문제가 말이 많은데 이해하기 힘든건 아니고, 결론만 말하자면 각 주사위별로

1. 기약분수를 먼저 구하고

2. 기약분수 분모 부분의 X-2의 제곱을 활용해 모듈로 역원을 구하고 (X가 1000000007)

3. 기약분수 분자와 저 모듈로 역원을 곱한 것의 모듈로를 구함.

그리고 위 값들에 대해 모듈로 누적합을 하면 된다.

이 때 최대공약수는 나머지 정리를 활용한 유클리드 호제법을 활용한다.

저 거대한 제곱수는 분할 정복 형태로 구하면 빠르면서도 값이 이상하게 나오지 않도록 구할 수 있다.