백준 13172번: Σ

www.acmicpc.net/problem/13172

13172번: Σ

---

본문이 꽤 길지만 잘 읽어보면 기댓값의 선형성, 모듈러 곱셈 역원과 페르마 소정리 등의 내용을 담고 있는 좋은 글입니다.

 

입력제한으로 $ N_{i} $와 $ S_{i} $가 $ 10^{9}+7 $ 보다 작게 주어진다고 써져있으므로 페르마의 소정리를 그대로 적용할 수 있습니다.

 

모듈러 곱셈 역원을 페르마의 소정리로 계산할 때 $ O\left( logN \right ) $으로 구해주면 충분합니다.

 

이때 $S_{i}$가 $N_{i}$로 나눠떨어질 때와 아닐 때를 구분해줘야 합니다.

 

또 $\large \frac{S_{i}}{N_{i}}$를 기약분수로 만들어줘야 하므로 유클리드 호제법으로 $S_{i}$와 $N_{i}$의 최대공약수를 구해줬습니다.

 

코드는 다음과 같습니다.

 

#include <stdio.h>

long long GCD (long long x, long long y); // GCD(x, y)
long long inverse_modular (long long N, long long P); // N^-1 mod P, P is prime number

int main() {
	
	int M;
	scanf("%d", &M);
	
	long long N, S, E; // E = expected value
	long long sum  = 0;
	
	int i;
	for (i = 0; i < M; i++) {
		
		scanf("%lld %lld", &N, &S);
		
		if (S % N == 0) {
			E = S / N;
		}
		else {
			long long gcd = GCD (N, S);
			N /= gcd;
			S /= gcd;
			E = (S * inverse_modular(N, 1000000007)) % 1000000007;
		}
		
		sum = (sum + E) % 1000000007;
	}
	
	printf("%lld", sum);
	
	return 0;
}

long long GCD (long long x, long long y) {
	long long temp;
	while (y > 0) {
		temp = x % y;
		x = y;
		y = temp;
	}
	return x;
}

long long inverse_modular (long long N, long long P) {
	long long result = 1;
	long long base = N;
	long long power = P - 2;
	while (power) {
		if (power & 1) {
			result = (result * base) % P;
		}
		base = (base * base) % P;
		power >>= 1;
	}
	return result;
}

 

(C11, 1116KB, 8ms, 제출번호 25927294)

---

본문이 길긴 했지만 나름대로는 친절한 문제였습니다.