[백준] 13172 Σ [자바]

 

---

https://latte-is-horse.tistory.com/9

[RSA] 페르마의 작은 정리와 오일러 정리

 

https://blog.yjyoon.dev/boj/2021/11/23/boj-13172/

[BOJ] 백준 13172번 Σ 풀이

 

 

※. 모듈러 연산 : a mod b = c -> 나머지를 구하는 연산

(26 mod 5 ≡ 36 mod 5)

 

※. 모듈러 역원 : 어떤 정수 p에 대해 (p * q) mod n ≡ 1

 

※ 페르마의 소정리(a,p는 서로소)

 

페르마의 소정리 역원

 

임의의 소수 X에 대한 b의 모듈러 곱셈에 대한 역원은 b^(X-2)이다.

 

※. 문제에 X는 1,000,000,007이므로 b^(1,000,000,007 - 2)를 구해야한다.

 

https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-1629%EB%B2%88-%EA%B3%B1%EC%85%88-CC

[백준] 1629번 : 곱셈 [C/C++]

https://tu-tr.tistory.com/160

[백준] 10830 행렬 제곱 [자바]

※. N,S를 gcd(s,n)으로 나누어주어 기약분수로 만든다.

  그 후 S * N^(X-2) mod X 를 ans에 더해준다.

 

---

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static long MOD = 1_000_000_007L;
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		//StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int M = Integer.parseInt(br.readLine());
		long ans = 0;
		for(int i = 0; i < M; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int N = Integer.parseInt(st.nextToken());
			int S = Integer.parseInt(st.nextToken());
			int g = gcd(Math.max(N, S), Math.min(N, S));
			N /= g;
			S /= g;
			ans += S * f(N,MOD-2) % MOD;
			ans %= MOD;
		}
		System.out.println(ans);
	}
	static int gcd(int a, int b) {
		if(b == 0)
			return a;
		return gcd(b, a%b);
	}
	static long f(long b, long n) {
		if(n == 1) return b;
		long p = f(b,n/2);
		long ret = p*p%MOD;
		if(n%2 == 1) {
			ret = ret*b%MOD;
		}
		return ret;
	}
}