정수론

정수론(Number theory)은 수학의 한 분야입니다.

그 중에서 프로그래밍 대회에 기본적으로 자주 나오는 기법을 소개합니다.

빠르게 소수를 찾는 기법인 에라토스테네스의 체

빠르게 최대공약수(Greatest Common Divisor)를 찾는 기법인 유클리드 알고리즘

C언어에서의 표현할 수 있는 수의 범위가 제한 되어있기에 큰 수 연산에 사용되는 나머지 연산

나누기의 나머지 연산을 대신하여 사용하는 나머지 연산의 곱셈 역원

이를 구하는 두가지 방법인 확장 유클리드 알고리즘과 페르마의 소정리를 알아두시면 좋습니다.

기본 문제

1929번: 소수 구하기

2609번: 최대공약수와 최소공배수

10430번: 나머지

11401번: 이항 계수 3