BOJ_13172_Σ_java

BOJ_13172_Σ

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

/**
 백준 13172 Σ
 골드 4
 */
public class BOJ_13172_Σ {
    static final int moduler = 1000000007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int M = Integer.parseInt(br.readLine());
        int[] N = new int[M];
        int[] S = new int[M];
        int ans = 0;

        for(int i = 0; i<M; i++){
            st = new StringTokenizer(br.readLine());
            N[i] = Integer.parseInt(st.nextToken());
            S[i] = Integer.parseInt(st.nextToken());
            int gcdVal = gcd(N[i], S[i]); // 기약분수
            int a = S[i] / gcdVal;
            int b = N[i] / gcdVal;
            ans += a * getInverseElement(b, moduler -2) % moduler;
            ans %= moduler;
        }
        System.out.println(ans);
    }

    public static long getInverseElement(int b, int exp){ // 역원 구하기
        if(exp == 1){ // 거듭제곱 수가 1인경우
            return b;
        }
        if(exp%2 == 1){ // 거듭제곱 수가 홀수인경우
            return b * getInverseElement(b, exp-1) % moduler;
        }
        long tmp = getInverseElement(b, exp/2);
        return tmp * tmp % moduler; // 거듭제곱 수가 짝수인경우
    }

    public static int gcd(int a, int b){ // 최대 공약수
        if(a<b){
            int tmp = a;
            a = b;
            b = tmp;
        }
        while(b!=0){
            int r = a%b;
            a = b;
            b = r;
        }
        return a;
    }
}