Exponial (오일러 정리 및 지수 순환 정리 활용)
문제 링크: http://acm.csu.edu.cn/csuoj/problemset/problem?pid=2021
설명
매우 큰 수를 좋아하는 사람들은 이 문제를 관심 있게 읽을 것입니다. 다음은 대규모 수 생성 방법의 예시입니다:
거듭제곱: 42^2016 = 42 × 42 × ... × 42 (2016번 반복)
팩토리얼: 2016! = 2016 × 2015 × ... × 2 × 1
이 문제에서는 'exponial'이라는 연산을 탐구합니다. 모든 양의 정수 n에 ...
7월 2일 05:14에 게시됨
확장 유클리드 알고리즘과 모듈러 역원의 원리 및 활용
확장 유클리드 알고리즘은 기본적인 최대공약수(GCD) 계산을 넘어, 선형 디오판토스 방정식 \(ax + by = \gcd(a, b)\) 의 정수해를 구하는 데 사용된다. 이는 특히 모듈러 산술에서 역원을 구할 때 핵심적으로 활용되며, 암호학이나 수치 해석 분야에서 중요하게 다뤄진다.
기본 개념 및 작동 원리
유클리드 알고리즘은 두 정수 \(a\)와 \(b\)에 대해 \(\gcd(a, b) = \gcd ...
6월 17일 22:32에 게시됨