모듈러 역원와 페르마의 소정리

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

13172번: Σ

모듈러 역원에 대해서 잘 설명해 놓은 문제이다.

 

핵심은 7/3 과 같은 분수를 답으로  하는 문제들을 판별하기 위해 a × b ^(-1) mod X 형태로 만드는것이다.

여기서 b^-1 이 모듈러 곱셈의 역원이다.

 

ll dq(ll a, ll b) 
{
	if (b == 1) 
		return a;

	if (b % 2 == 1) 
		return a * dq(a, b - 1) % MOD;

	ll c = dq(a, b / 2);

	return c * c % MOD;
}

for (int i = 0; i < N; i++)
{
	cin >> b >> a;

	ll mok = gcd(a, b);
	b /= mok;
	a /= mok;
	ans += a * dq(b, MOD - 2) % MOD;
	ans %= MOD;
}

 

 

문제 나와있지만 중요한것은 페르마의 소정리이다. 소수 에서만 성립하는 정리이기때문에 이와 gcd를 활용하면 모듈러 곱셈의 역원을 구해 나눗셈을 알 수 있다.