[JAVA] 백준 13172 - Σ

https://www.acmicpc.net/problem/13172

문제 설명이 굉장히 긴 문제였지만 결론적으로 a/b를 기약분수 형태로 만들고, b의 모듈러 연산의 역원을 구해 

주사위 1개 당 a * b-1 % 1000000007의 값을 구해 그 합을 구하는 문제였다.

 

일단 a/b를 기약분수 형태로 만들기 위해 유클리드 호제법(퍼플렉시티한테 물어봄)을 통해 최대공약수를 구하고, 페르마의 소정리 (퍼플렉시티한테 물어봄) 로 b의 모듈러 연산의 역원을 구해 이를 a에 곱해주고 나머지를 구했다. 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        long mod = 1000000007;
        int testcase = Integer.parseInt(s);
        long answer = 0;
        for (int i = 0; i < testcase; i++) {
            long[] arr = Arrays.stream(br.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
            long a = arr[0];
            long b = arr[1];
            long gcd = getGcd(a,b);
            a/=gcd;
            b/=gcd;
            long inverse = getFastPow(a,mod-2,mod);
            answer = answer + (b*inverse%mod);
        }
        System.out.println(answer%mod);
    }

    static long getGcd(long a, long b) {
        long rest = a % b;
        while (rest != 0) {
            long temp = rest;
            rest = b % rest;
            b = temp;
        }
        return b;
    }

    static long getFastPow(long a, long target, long mod){
        long answer = 1;
        while(target!=0){
            if((target&1)==1){
                answer = (answer * a)%mod;
            }
            a = (a * a) %mod;
            target>>=1;
        }

        return answer;
    }
}

 

문제를 읽는게 어려운 문제였다.