백준 BOJ 13977 - 이항 계수와 쿼리

페르마의 소정리 사용 문제.

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

13977번: 이항 계수와 쿼리

페르마의 소정리에 대해서는 백준님이 깔끔하게 정리해 주셨습니다.

https://www.acmicpc.net/blog/view/29

 

페르마의 소정리를 통해 역원을 구해주면, 역원의 곱을 통해 나눗셈을 대체할 수 있으며,

따라서 mod연산을 할때 나눗셈을 하지않고 구할수 있게 됨.

쿼리가 10만개를 넘기 때문에, O(logN)시간에 제곱연산을 수행해주는 함수 pow를 직접 작성하엿고,

mod연산을 완료한 팩토리얼값을 모두 배열에 저장해

빠르게 접근할수 있도록 해주면 AC가 나옴.

 

#include <stdio.h>
#define MOD 1000000007

typedef long long int ll;

ll fac[4000010] = {0};
ll pow(ll a, ll b){
	if(b==0)   return 1;
	if(b%2==1) return (a*pow(a,b-1) % MOD) % MOD;
	else       return pow((a*a) % MOD, b/2) % MOD;
}


int main(){
	fac[0] = 1;
	fac[1] = 1;
	for(int i=1; i<=4000000; i++)fac[i+1] = ( fac[i] * (i+1) ) % MOD;
	
	int m,n,k;
	scanf("%d", &m);
	while(m--){
		scanf("%d %d", &n, &k);
		ll tmp = (fac[k]*fac[n-k] % MOD);
		printf("%lld\n", fac[n] * pow(tmp, MOD-2) % MOD);
	} 
	return 0;
}

pow함수에도 MOD를 넣어주어야 오버플로우가 일어나지 않는다.