[BOJ] 13172 Σ - JAVA

1. 문제

13172번: Σ

S1/N1 + S2/N2 + ... + SM/NM
 
b의 모듈러 곱셈에 대한 역원 b-1은 대체 어떤 수인 것일까? 이 수는 다음과 같은 성질을 만족하는 정수이다.
b^-1 × b ≡ 1(mod X)
소수 모듈러에서만 성립하는 페르마의 소정리에 의해 b^(X - 1) ≡ 1 (mod X)가 성립하기에, b^(X - 2) ≡ b-1 (mod X) 역시 성립함을 알 수 있다.
 
이제 이 방식으로 M 개의 주사위가 있고, i번째 주사위가 Ni면체 주사위이며, 모든 면에 적힌 숫자를 더한 값이 Si일 때, 각 주사위에 대해서 주사위를 던졌을 때 주사위의 각 면이 나올 확률이 동일하다면, 모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 구하는 문제를 해결해보자.
 
첫 번째 줄에는 주사위의 수를 나타내는 정수 M(1 ≤ M ≤ 104)이 주어진다.
다음 M개의 줄은 각 주사위의 정보를 나타내며, 이 중 i(1 ≤ i ≤ M)번째 줄에는 Ni, Si(1 ≤ Ni, Si ≤ 109)가 공백으로 구분되어 주어진다.

---

2. 풀이

이 문제에서 핵심적으로 알아야 할 부분은 분할정복을 이용한 거듭제곱 풀이다. https://www.acmicpc.net/problem/1629 이 문제를 먼저 풀어보길 바란다.

Main

1.  주사위 개수 M개만큼 N,S를 입력받아서 결과에 더한다. 더할 때마다 mod연산을 해야 한다.
2.  계산 후 result를 출력한다.

static int MOD = 1_000_000_007;
public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   int M = Integer.parseInt(in.readLine());
   StringTokenizer st;
   long result = 0;
   int N, S;
   for(int i=0;i<M;i++){
      st = new StringTokenizer(in.readLine());
      N = Integer.parseInt(st.nextToken())%MOD;
      S = Integer.parseInt(st.nextToken())%MOD;
      result = (result + calc(S,N))%MOD;
   }

   System.out.println(result);
}

 

거듭제곱

a^b를 분할정복을 이용해 계산한다.
b==1이면 a를 반환한다.
a^b = a^(b/2) * a^(b/2) 임을 이용해서 풀이한다.
다만, b가 홀수일 경우 a^(b/2) * a^(b/2) 에 a를 한 번 더 곱한다.

private static long pow(int a, int b){
   if(b==1) return a;
   long res = pow(a,b/2);
   res = res*res%MOD;
   return b%2!=0? res*a%MOD:res;
}

 

최대공약수

gcd(a,b)=gcd(b,a%b)를 이용한다.
 
a가 b보다 작을 경우 교체한다.
b가 0이면 a를 반환한다.
아니라면 gcd(b,a%b)값을 반환한다.

private static int gcd(int a, int b){
   if(a<b){
      int tmp = a;
      a = b;
      b = tmp;
   }

   if(b==0) return a;
   return gcd(b, a%b);
}

 

기댓값 계산

먼저 문제에서 기약분수 기준 식을 설명했으므로 a, b의 최대공약수를 구해서 기약분수로 만든다.
 
a * b^-1 = a * b^(X-2) 이기 때문에 a * pow(b,MOD-2)를 반환한다.
이때, a와 a * pow(b,MOD-2) 결과값 모두 %연산이 필요하다.
pow(b,MOD-2)에 하지 않는 이유는 메서드에서 값을 반환할 때 이미 %연산을 끝냈기 때문이다.

private static long calc(int a, int b){
   int g = gcd(a,b);
   a /= g;
   b /= g;

   return (long)a%MOD*pow(b,MOD-2)%MOD;
}

 

전체 코드

import java.io.*;
import java.util.*;

public class BOJ_13172_Σ {
   static int MOD = 1_000_000_007;
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      int M = Integer.parseInt(in.readLine());
      StringTokenizer st;
      long result = 0;
      int N, S;
      for(int i=0;i<M;i++){
         st = new StringTokenizer(in.readLine());
         N = Integer.parseInt(st.nextToken())%MOD;
         S = Integer.parseInt(st.nextToken())%MOD;
         result = (result + calc(S,N))%MOD;
      }

      System.out.println(result);
   }

   private static long pow(int a, int b){
      if(b==1) return a;
      long res = pow(a,b/2);
      res = res*res%MOD;
      return b%2!=0? res*a%MOD:res;
   }
   
   private static int gcd(int a, int b){
      if(a<b){
         int tmp = a;
         a = b;
         b = tmp;
      }

      if(b==0) return a;
      return gcd(b, a%b);
   }

   private static long calc(int a, int b){
      int g = gcd(a,b);
      a /= g;
      b /= g;

      return (long)a%MOD*pow(b,MOD-2)%MOD;
   }
}

---

3. 결과

b*b^-1 = 1(mod x)라고 하길래 b^-1를 (mod+1)/b한 값으로 생각했다가 대차게 틀렸다.
문제에 주어진 식은 꼼꼼하게 전부 활용하자 ..!