[백준] 13172번 : Σ [C/C++]

#문제

13172번: Σ

https://www.acmicpc.net/problem/13172

13172번: Σ

 

---

#접근방법

이 문제를 처음 봤을 때 글이 너무 많고, 또 이해하기가 힘들었다. 두 세번정도 읽으니 전체적인 맥락과 수식들이 눈에 보여서 이해가 되었다. 페르마 소정리와 모듈러 역원에 대해 자세하게 적은 글이다.

 

다른건 다 필요없고 b^(x-2) ≡ b^-1 (mod X) 이 수식에서 b^(x-2) 이것을 구하는 것이 핵심이다.

반응형

---

#풀이

#include <stdio.h>
#include <numeric>
using namespace std;

using ll = long long;
ll MOD = 1'000'000'007;

ll f(ll x, ll y){
	if(y==1) return x;
	if(y%2==1) return x*f(x,y-1)%MOD;
	ll p = f(x,y/2);
	return p*p%MOD;
}

int main(){
	ll m,a,b;
	ll ans = 0;
	
	scanf("%lld",&m);
	
	while(m--){
		scanf("%lld %lld",&b,&a);
		ll g = gcd(a,b);
		b /= g;
		a /= g;
		ans += a*f(b,MOD-2)%MOD;
		ans%=MOD;
	}
	
	printf("%lld",ans);
	
	return 0;
}

 

b와 a를 입력받으면 두 수를 gcd (최대공약수)를 구해서 나눠주면 더 이상 나눌 수 없는 기약분수의 형태로 나타낼 수 있다. gcd함수를 쓰려면 #include <numeric>라는 헤더파일을 써야한다.

 

기약분수를 구했으면 이제 위에서 설명한 것 처럼 b^(x-2) 이것을 구하는 것이 핵심인데 x = 1'000'000'007이라면 b^1'000'000'005를 구해야 한다.

곱셈으로 구하면 시간초과가 걸리므로 거듭제곱을 O(log n)의 시간복잡도로 구해야 한다.

 

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++]

 

여기에 나와있는 방식으로 구하면 O(log n)의 시간복잡도로 구할 수 있다.

 

그리고 ans에 값을 누적시키면서 MOD로 나머지를 계속 구해주면 정답이다.

---

#성능

---

#정리

문제를 이해해서 핵심을 파악하는 것,

 

같은 수를 거듭제곱할 때, O(log n)의 시간복잡도로 구하는 방법을 알고 있으면 풀 수 있는 문제였다.