백준 11401

#c 언어 #이항계수 #모듈러 역원 # 페르마의 소정리 #이진 곱셈

 

먼저 이항계수 구하는 방법..

 

볼 때마다 기억이 나지 않아서 찾아보는 내가 싫다..

 

당연히 모듈러 연산이니까 덧셈, 곱셈처럼 계신해주면 된다고 생각했는데 나눗셈 연산은 그렇게 계산하는게 아니란다..

 

나누기 연산은 나누는 숫자의 역원을 구하여 곱해주는 것이 맞음

 

 

이때 [페르마의 소정리]와 [확장 유클리드 호제법]이 있음.

 

페르마의 소정리는 나누는 숫자가 소수여야 한다는 제한이 있고

확장 유클리드 호제법은 연산에 사용되는 두 숫자가 서로소여야 한다는 조건이 있음

 

여기서는 m 이 1000000007로 소수이기 때문에 페르마의 소정리를 이용한다.

 

 

(n * n-1 * ...* k+1) / (n-k * n-k-1 * ...* 2) 의 연산을 해주면 된다

 

gpt를 이용하여 사용법을 알아냄..ㅋ ㅋ

 

즉 나눠주는 숫자 a의 역원은 a를 1000000007-2 제곱해준 숫자를 1000000007 으로 나눈 나머지와 같음.

 

 

처음에는 역원을 구할 떄 for문으로 구하려 했는데 

이진 곱셈법을 사용하여 시간을 더 줄일 수 있다는걸 알게됨..!

long long modv(long long x, long long n) {
	long long total = 1;
	x %= m;
	while (n > 0) {
		if (n % 2 == 1) { // n이 홀수인 경우
			total = (total * x) % m;
		}
		x = (x * x) % m; // x를 제곱하고
		n /= 2;          // 지수를 반으로 줄임
	}
	return total;

n이 홀수일 때는 x를 한번 곱해주고 짝수일 떄는  x의 제곱 연산과 n을 절반으로 나눠줘 계산 횟수를 크게 줄일 수 있음!!

 

또한 k가 0일 경우 0!은 1이기 때문에 이점에 주의해줄 것..