아이디어

• 문제를 잘 읽고 문제에서 제시된 모듈로 연산, 모듈로 역원과 페르마의 소정리를 잘 구현하면 되는 문제
  • $X=1\ 000\ 000\ 007$일 때 $S_1N_1^{X-2} + S_2N_2^{X-2} + ... + S_MN_M^{X-2} \pmod{X}$를 계산하면 된다.
• 거듭제곱을 구할 때는 분할정복을 사용한다.

코드

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

public class Main {
	static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tk = null;

	static int M, N, S, ans;

	static final int X = 1_000_000_007;
	
	public static void main(String[] args) throws Exception {
		M = Integer.parseInt(rd.readLine());
		
		for(int i=0; i<M; i++) {
			tk = new StringTokenizer(rd.readLine());
			N = Integer.parseInt(tk.nextToken());
			S = Integer.parseInt(tk.nextToken());
			
			ans = add(ans, times(S, pow(N, X-2)));
		}
		
		System.out.println(ans);
	}
	
	static int add(int a, int b) {
		return (a + b) % X;
	}
	
	static int times(int a, int b) {
		return (int) ((long) a * b % X);
	}
	
	static int pow(int a, int n) {
		if (n == 1) return a;
		
		int r = pow(a, n/2);
		r = times(r, r);
		if (n % 2 == 1)
			r = times(r, a);
		return r;
	}
}

메모리 및 시간

• 메모리: 19960 KB
• 시간: 228 ms

리뷰

• 어제와 비슷한 정수론 문제
• 튜토리얼인가? 생각이 들만큼 문제가 친절하다